Calculating all possible combinations of a string, with a twist

Question

I'm trying to allow a user to enter text in a textbox, and have the program generate all possible combinations of it, except with a minimum of 3 characters and maximum of 6. I don't need useless words like 'as', 'a', 'i', 'to', etc cluttering up my array. I'll also be checking each combination against a dictionary to make sure it's a real word.

I have the dictionary complete (painstakingly generated, here's a link to it in return (WARNING: gigantic load time (for me)!)

Anyways, if the user enters 'ABCDEF' (in no particular order), how could I generate, for example:

'ABC'
'BAC'
'CAB'
...
'ABD'
'ABE'
'ABF'

etc... EVERY possible combination, no matter what order? I understand that there are a ridiculous amount of these combinations, but it only needs to be calculated once, so I'm not too worried about that.

I've found code samples to recursively find combinations (not permutations, I don't need those) of just the fixed-width string (ABCDEF, ABCDFE ... ACDBFE, etc). They don't do what I need, and I haven't the slightest clue about where to even start with this project.

This isn't homework, it started out as a personal project of mine that's grown to take over my life over such a simple problem... I can't believe I can't figure this out!

Answer 1

It sounds to me like you're describing the Power Set

Here's an implementation I had lying around my personal library:

// Helper method to count set bits in an integer
public static int CountBits(int n)
{
    int count = 0;
    while (n != 0)
    {
        count++;
        n &= (n - 1);
    }
    return count;
}


public static IEnumerable<IEnumerable<T>> PowerSet<T>(
    IEnumerable<T> src, 
    int minSetSize = 0, 
    int maxSetSize = int.MaxValue)
{
    // we want fast random access to the source, so we'll
    // need to ToArray() it
    var cached = src.ToArray();
    var setSize = Math.Pow(2, cached.Length);
    for(int i=0; i < setSize; i++)
    {
        var subSetSize = CountBits(i);
        if(subSetSize < minSetSize || 
           subSetSize > maxSetSize)
        {
            continue;
        }
        T[] set = new T[subSetSize];

        var temp = i;
        var srcIdx = 0;
        var dstIdx = 0;
        while(temp > 0)
        {
            if((temp & 0x01) == 1)
            {
                set[dstIdx++] = cached[srcIdx];
            }
            temp >>= 1;
            srcIdx++;            
        }
        yield return set;
    }
    yield break;
}

And a quick test rig:

void Main()
{
    var src = "ABCDEF";
    var combos = PowerSet(src, 3, 6);

    // hairy joins for great prettiness
    Console.WriteLine(
        string.Join(" , ", 
            combos.Select(subset => 
                string.Concat("[", 
                    string.Join(",", subset) , "]")))
    );
}

Output:

[A,B,C] , [A,B,D] , [A,C,D] , [B,C,D] , [A,B,C,D] , [A,B,E] , [A,C,E] , [B,C,E] , [A,B,C,E] , 
[A,D,E] , [B,D,E] , [A,B,D,E] , [C,D,E] , [A,C,D,E] , [B,C,D,E] , [A,B,C,D,E] , [A,B,F] , 
[A,C,F] , [B,C,F] , [A,B,C,F] , [A,D,F] , [B,D,F] , [A,B,D,F] , [C,D,F] , [A,C,D,F] , 
[B,C,D,F] , [A,B,C,D,F] , [A,E,F] , [B,E,F] , [A,B,E,F] , [C,E,F] , [A,C,E,F] , [B,C,E,F] , 
[A,B,C,E,F] , [D,E,F] , [A,D,E,F] , [B,D,E,F] , [A,B,D,E,F] , [C,D,E,F] , [A,C,D,E,F] , 
[B,C,D,E,F] , [A,B,C,D,E,F]

Answer 2

Supposed, you also want stuff like "AAB" the "cross product" of your set of letters should be it.

Generation can be as simple as a LINQ:

            string myset = "ABCDE";
            var All = (from char l1 in myset 
                   from char l2 in myset 
                   from char l3 in myset 
                   select new string(new char[] { l1, l2, l3})).ToList();

Note: construction many strings and char Arrays is not fast. You may want to replace the new string and new char[] with a custom class like so:

select new MyCustomClass(l1, l2, l3).ToList();

If you don't want things like "AAB" (or "EEL") then I'd point you to wikipedia for "combinations".

To get from fixed-length to "any length from 3 to 6" join multiple sets, if the limits are dynamic then use a loop.

Answer 3

The best way to do this is to use a for loop and convert each character from an int to a char and concatenate them together in a string.

For example:

for(int i = 0; i < 26; i++)
{
    Console.WriteLine((char)i + 'A');        
}