перебор всех возможных вариантов или тупая комбинаторика
Часто так бывает (например сегодня мне нужно было это сделать, поэтому сообственно и вышел этот пост), что нужно найти все комбинации символов из какого-то определенного алфавита. Например вы знаете из каких символов состоит пароль и знаете примерную длину, скажем от 5 до 7 символов, и вам надо перебрать все возможные комбинации.
Раздел математики под названием Комбинаторика по этому поводу говорит, что количество таких комбинаций с повторами будет равно Nm, где N – размер алфавита, а m – максимальное количество символов в комбинации(слове).
И комбинаторика действительно не врет, в этом можно легко убедится напримере:
A={1,0} => N=2
m=3
001
010
011
100
101
110
111
Nm=23=8. Что и требовалось доказать.
Посчитать-то количество мы смогли, а вот конкретно найти все возможные варианты нам поможет следующий скрипт.
Сначала зададим алфавит и максимальное количество символов в слове:
alf=['a','l','f','v','i','t']
max_size=5
Теперь немного объясню принцип.
Он такой же как и был на примере, где убеждались в правоте комбинаторики. Короче, мы ставим нашему алфавиту в соответсвие цифру из системы счисления равной длине алфавита. В нашем случае это будет шестиричная система счисления. Далее мы просто будем инкрементно крутить какую-то переменную скажем i т.е. будем в цикле прибавлять к i единицу.
Но для начала нам нужно посчитать сколько нужно шагов в цикле, чтобы длина слова соответствовала max_size.
res=alf.size**max_size
Тупо пользуемся этой самой формулой из комбинаторики.
А теперь также тупо будем инкрементно крутить в цикле переменную i и обратно ставить в соответсвие каждой цифре числа символ из алфавита:
for i in 2..res+1 do
str=”
i.to_s(alf.size).scan(/./).each {|x| str+=alf[x.to_i]}
puts “#{i} – #{i.to_s(7)} – #{str}”
end
Весь приведенный здесь код написан на Ruby.
Я закончил, а теперь каждый случайно заглянувший сюда великий математик или программист может плюнуть в монитор, написать отрицательный коммент и просебя матернутся: мол это и ежу понятно, мол существуют гораздо менее ресурсотребовательные способы итд.
//порадовал последний абзац.
//хотел кое-что проверить и полез в инет за умными мыслями по теме перебора (составить комбинацию из count проводов).
//Вы не поверите, ваша статья самая умная по этому вопросу.
//я сделал так:
bool is_original(int *digit,int count);
void pripri(int *digit,int count)
{
for(int i=1;i<count+1;i++)printf("%i",digit[i]);
if(is_original(digit,count))printf(" =0 && perenos==1;i–)
{
if(digit[i]+1==count)
{
digit[i]=0;perenos=1;
}
else
{
digit[i]++;perenos=0;
}
}
if(digit[0]!=0)return false;else return true;
}
bool is_original(int *digit,int count)
{
for(int i=1;i<count+1;i++)
{
for(int j=i+1;j<count+1;j++)
{
if(digit[i]==digit[j])return false;
}
}
return true;
}
int _tmain(int argc, _TCHAR* argv[])
{
int count=3;
int *digit=new int[count+1];
for(int i=0;i<count+1;i++)digit[i]=0;
do
{
while(!is_original(digit,count))plusplus(digit,count);
pripri(digit,count);
}while(plusplus(digit,count));
return 0;
}
Пасибо за помощь в осеку , так же пригодилась статья для проверки
.scan(/./).each можно заменить на .each_char