Generating ALL possible combinations

[proff.hacker]

Hi everybody,

I have an array of letter for example:

string strings[] = { "a", "b", "c", "d", "e"};

I want to generate all possible combinations of a specific length which is determined by the user, for example when he selects 3:

aaa
aab
aac
aad
aae
aba
abb
abc
abd
abe
abd
aca
acb
acc
acd
ace

etc...


I started by this code but it's limited to the length I assume before the runtime

foreach (string l1 in strings)
            {
                foreach (string l2 in strings)
                {
                    foreach (string l3 in strings)
                    {
                        myword = l1 + l2 + l3;
                    }
                }
            }

can you think of any solution that works with any length selected by the user at runtime?

Thanks

[jmcilhinney]

A generic algorithm would use three loops. You'd create a StringCollection that contained all possible one-letter combinations. You'd then have an outer for loop that iterated from 2 to the length of the fiianl strings you want, which is 3 in the example you provided. You then have an inner For Each loop that iterated over all the items of your current StringCollection, then iside that another For Each loop that iterated over all the characters in your array. You would then create a new StringCollection inside that third loop by concatenating the character to the current string and adding it to the new collection. That new collection now becomes your existing collection and you start a new iteration of the outer loop. I'm guessing homework of some kind so I'll leave the implementation up to you.

[jmcilhinney]

Here's a start:

int finalLength = 3; // The length of the final strings.
string[] characters = new string[] { "a", "b", "c", "d", "e" };
System.Collections.Specialized.StringCollection existingStrings;
System.Collections.Specialized.StringCollection newStrings;

// Start with the all one-letter combinations.
newStrings.AddRange(characters);

for (int i = 2; i <= finalLength; i++)
{
    // Start a new collection of strings based on the existing strings.
    existingStrings = newStrings;
    newStrings = new System.Collections.Specialized.StringCollection();

    // Put the other loops here.
}

[proff.hacker]

Hi

First of all, thanks for your help.

Actually, it's not a homework but I am trying to make a bruteforce tool for a hashing function

I didn't understand your approach, for example what if I want to generate all 5-letter strings.

It would be great if you could kindly complete your code, it will save alot of time

Thanks again

[jmcilhinney]

int finalLength = 3; // The length of the final strings.
string[] characters = new string[] { "a", "b", "c", "d", "e" };
System.Collections.Specialized.StringCollection existingStrings;
System.Collections.Specialized.StringCollection newStrings = new System.Collections.Specialized.StringCollection(); // Start with the all one-letter combinations.

newStrings.AddRange(characters);

for (int len = 2; len <= finalLength; len++)
{
    // Start a new collection of strings based on the existing strings.
    existingStrings = newStrings;
    newStrings = new System.Collections.Specialized.StringCollection();

    // Concatenate every string of length (len-1)...
    foreach (string str in existingStrings)
    {
        // ...with every character...
        foreach (string ch in characters)
        {
            // ...to create every possible string of length len.
            newStrings.Add(str + ch);
        }
    }
}

All you need to do is change the value of 'finalLength' to however many characters you want in all the final strings. You could also accomplish this task using recursion if you wanted as it's a prime candidate.

[proff.hacker]

Great, thanks man it works like a charm

Which approach is better if we take performance and speed into consideration?

Also how can I use concatenated strings in the most inner loop (i.e 3rd loop) so that I can directly compare the generated string with a certain string without implementing another loop that iterates over newStrings collection

Regards

[jmcilhinney]

Recursion is often easier to write, as long as you understand the principle properly, but iteration will generally be more efficient. That's unless you have to tie yourself in knots to achieve it using interation.

Collections have a Contains method. If you're using an array there is Array.IndexOf.

[proff.hacker]

Contains will work if I want to find something in the original collection

but I don't want that, I want for example to encrypt the string and then to print it

I tried something like this inside the most inner loop but I got index out of range exception

int w=0;
....
....
// ...to create every possible string of length len.
newStrings.Add(str + ch);
Console.WriteLine(newStrings[w]);
w++;

[jmcilhinney]

I don't understand what you're trying to achieve with that. If you want to get the last string in the collection then just use newStrings[newStrings.Count - 1]. Otherwise you're going to have to explain your aim.

[proff.hacker]

I want to print all generated strings, I think it's clear now