Reputation: 41
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
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
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