CODEWITHSUNDEEP
c#wildcardpermutationcombinations
user1146631
user1146631

Reputation: 41

generate all permutations of a word with wildcard

I need to recover a password of mine, and I know some of the letters, but forget what characters I used for the rest. I need a way to generate all possible permutations of the password, given some known characters and some unknown. For example, I would want to enter a phrase like "mic??s??t" into a textbox, and the program would generate all possible permutations of that. In this case, I know only a few characters are possibly used in place of those question marks, but I would like the program to have the option of permuting all characters A-Z, a-z, 0-9, /symbols/, etc, OR a specific set of characters like E-G, t-y, 1-4, etc, takin in via a second textbox as a string.

using all characters, it might generate a list like

micAAsAAt

micAAsABt

micAAsACt

micAAsADt

....

using a limited set of characters such as E-G only it would look like

micEEsEEt

micEEsEFt

micEEsEGt

micEEsFEt

micEEsFFt

....

If the only way to do this is to generate every permutation period, wildcard or not, for a word of N length, then checking each one with a regex pattern to filter out the useless ones, I can accept that (it would generate 256^N possible combos though). Otherwise, I'd rather be able to generate an array of all possible ones just using recursion (which I need help with). In the end, I would like to produce a txt file list of these permutations. I really need the help with the recursion here. I use C#.

Upvotes: 3

Views: 2309

Answers (2)

Adam S
Adam S

Reputation: 3125

Here is a simple solution that blends a recursive and iterative approach. I suppose a fully recursive solution could be implemented, but I find this approach much easier to understand.

//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));
    }
}

Call to the function would be:

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

GenerateCombos(mask, combination);

Upvotes: 2

Jon Hanna
Jon Hanna

Reputation: 113392

It's actually combinations rather than permutations.

Anyway, why use recursion?

Recursion is used because we can think of a solution that works in a recursive way, and so we program to match. Often the compiler isn't able to optimise it into a faster and smaller iterative version, but that's normally fine. But if you can't think of a recursive approach yourself, then why look for help with it, rather than with an iterative approach?

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);
        }
    }
}

This should give us 81 different strings (3 to the power of four). And it does. Calling Distinct() on it to make sure a bug isn't creating duplicates still gives us 81. Happy days.

Upvotes: 0

Related Questions