генерировать все перестановки слова с подстановочными знаками - PullRequest
Новая
       18

генерировать все перестановки слова с подстановочными знаками

2 голосов
/ 13 января 2012

Мне нужно восстановить свой пароль, и я знаю некоторые буквы, но забуду, какие символы я использовал для остальных.Мне нужен способ генерировать все возможные перестановки пароля, учитывая некоторые известные символы и некоторые неизвестные.Например, я хотел бы ввести фразу типа «mic ?? s ?? t» в текстовое поле, и программа сгенерирует все возможные варианты этого.В этом случае я знаю, что вместо этих вопросительных знаков возможно использовать только несколько символов, но я бы хотел, чтобы в программе была возможность перестановки всех символов AZ, az, 0-9, / symbols /, etc, ИЛИопределенный набор символов, таких как EG, ty, 1-4 и т. д., вводится через второе текстовое поле в виде строки.

при использовании всех символов может генерироваться список, например

micAAsAAt

micAAsABt

micAAsACt

micAAsADt

....

с использованием ограниченного набора символов, например только EG, это будет выглядеть как

micEEsEEt

micEEsEFt

micEEsEGt

micEEsFEt

micEEsFFt

....

Если единственный способ сделать это - генерировать каждый период перестановки, подстановочный знак или нет, для слова длиной N, а затем проверять каждый из них с помощью регулярного выражениячтобы отфильтровать бесполезные, я могу принять это (хотя это сгенерирует 256 ^ N возможных комбинаций).В противном случае, я бы предпочел сгенерировать массив всех возможных, просто используя рекурсию (с которой мне нужна помощь).В конце я хотел бы создать список этих перестановок в текстовом файле.Мне действительно нужна помощь с рекурсией здесь.Я использую C #.

Ответы [ 2 ]

1 голос
/ 13 января 2012

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

//List of characters to substitute in place of '?'
List<char> validChars = new List<char>() { 'w', 'x', 'y', 'z' };
//List of combinations generated
List<string> combos = new List<string>();

void GenerateCombos(string mask, string combination)
{
    if (mask.Length <= 0)
    {
        //No more chars left in the mask, add this combination to the solution list.
        combos.Add(combination);
        return;
    }

    if (mask[0] != '?')
    {
        //This is not a wildcard, append the first character of the mask
        //to the combination string and call the function again with 
        //the remaining x characters of the mask.
        GenerateCombos(mask.Substring(1), combination + mask[0]);
    }
    else
    {
        //This is a wildcard, so for each of the valid substitution chars,
        //append the char to the combination string and call again
        //with the remaining x chars of the mask.
        validChars.ForEach(c => GenerateCombos(mask.Substring(1), combination + c));
    }
}

Вызов функции будет: 

string mask = "mic??s??t";
string combination = String.Empty;

GenerateCombos(mask, combination);
0 голосов
/ 13 января 2012

Это на самом деле комбинации, а не перестановки.

В любом случае, зачем использовать рекурсию?

Рекурсия используется потому, что мы можем придумать решение, которое работает рекурсивно, и поэтому мы программируем для соответствия. Часто компилятор не может оптимизировать его в более быструю и меньшую итеративную версию, но это нормально. Но если вы не можете придумать рекурсивный подход самостоятельно, то зачем искать помощь с ним, а не с итеративным подходом? 

private IEnumerable<string> Combinations()
{
    //Let's just use a-c for a test run.
    string setOfChars = "abc";
    //Let's return for four characters to guess for. We can change this.
    char[] buffer = new char[4];
    //We'll change these indices and then use them to pick chars from
    //setOfChars to the corresponding place in buffer
    int[] setOfIndices = new int[buffer.Length];

    //set up initial position:
    for(int i = 0; i != buffer.Length; ++i)
        buffer[i] = setOfChars[0];

    //return our inital position.
    yield return new string(buffer);

    //Now for our actual combinations.
    for(int i = 0; i != buffer.Length; ++i)
    {
        if(++setOfIndices[i] == setOfChars.Length)
            //if we've pushed an index out of range, then set it back to zero.
            setOfIndices[i] = 0;
        else
        {
            //otherwise move our position for changing things back to zero
            i = -1;

            //and generate our new combination.
            for(int j = 0; j != buffer.Length; ++j)
            buffer[j] = setOfChars[setOfIndices[j]];
            yield return new string(buffer);
        }
    }
}

Это должно дать нам 81 различную последовательность (от 3 до 4). И это так. Вызов Distinct(), чтобы убедиться, что ошибка не создает дубликатов, все равно дает нам 81. Счастливые дни.

...