перебор всех возможных вариантов или тупая комбинаторика

Часто так бывает (например сегодня мне нужно было это сделать, поэтому сообственно и вышел этот пост), что нужно найти все комбинации символов из какого-то определенного алфавита. Например вы знаете из каких символов состоит пароль и знаете примерную длину, скажем от 5 до 7 символов, и вам надо перебрать все возможные комбинации.

Раздел математики под названием Комбинаторика по этому поводу говорит, что количество таких комбинаций с повторами будет равно Nm, где N – размер алфавита, а m – максимальное количество символов в комбинации(слове).
И комбинаторика действительно не врет, в этом можно легко убедится напримере:
A={1,0} => N=2
m=3

000
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.

Я закончил, а теперь каждый случайно заглянувший сюда великий математик или программист может плюнуть в монитор, написать отрицательный коммент и просебя матернутся: мол это и ежу понятно, мол существуют гораздо менее ресурсотребовательные способы итд.

3 Comments to “перебор всех возможных вариантов или тупая комбинаторика”

  1. FiREBALL пишет:

    //порадовал последний абзац.
    //хотел кое-что проверить и полез в инет за умными мыслями по теме перебора (составить комбинацию из 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;
    }

  2. nonamez пишет:

    Пасибо за помощь в осеку , так же пригодилась статья для проверки

  3. Misha пишет:

    .scan(/./).each можно заменить на .each_char

Leave a Reply to Misha

(обязательно)

(обязательно)