Breaking Down & Rearranging String into all possible combinations

I want to break down a开发者_运维技巧nd rearranging a string into all possible combinations

Say I have a String: ABCDEF

I want to break it down and output all possible combinations

Combination(6,6) = 1

ABCDEF

Combination(6,5) = 6

BCDEF
ACDEF
ABDEF
ABCEF
ABCDF
ABCDE

Combination(6,4) = 15

BCDE
ACDE
ABDE
ABCE
....
....
....
etc.

Combination(6,3) = 20

BCD
ACD
...
etc.

Combination(6,2) = 15 BC AB etc.

However the ouptut must also be arranged into alphabetical order.

How will I do this?

Thanks! Any help will be appreciated!

You can get the algorithm (actually a few of them) from Knuth Volume 4, Fascicle 3 but you'll have to convert it from his math notation to C#.

Update: As I think about this more, Fascicle 2 (Generating Permutations) is actually more helpful. You can download it free from http://www-cs-faculty.stanford.edu/~knuth/fasc2b.ps.gz though you'll need gunzip and a PostScript previewer to read it. Generating the subsets of string "ABCDE" is the easy part. Convert it to an array {'A', 'B', 'C', 'D', 'E'}, run a for loop from 0 to 2^N-1 where N is the array length, and treat each value as a bitmask of the elements you're keeping. Thus 00001, 00010, 00011,... gives you "A", "B", "AB",...

The hard part is generating all the permutations of each subset, so you get "ABC", "BAC", "CAB", etc. A brute force algorithm (like in one of the other answers) will work but will get very slow if the string is long. Knuth has some fast algorithms, some of which will generate the permutations in alphabetical order if the original string was sorted in the first place.

Well, to expand on my comment, how I got past this problem was transforming the string into a hash that doesn't care the order of the letters. The hash works by taking each unique letter, then a :, then the number of times that letter occurs.

So test = e:1,s:1,t:2

Then if somebody looks for the world tset, it would generate the same hash (e:1,s:1,t:2), and bam you have a match.

I just ran a word list (of about 20 million words), generated a hash for each one of them, and put it in a mysql table, I can find all permutations of a word (that are still words themselves, aka ered will return deer and reed) in seconds.

You can generate each permutation by incrementing a counter and converting the counter value to base n where n is the number of letters in your input. Discard any values containing repeating letters and what you have left are the possible scrabble words in alphabetic order assuming your array was sorted.

You will have to count up to (n^(n-1))*(n+1) to get the e*n! possible scrabble words.

char[] Letters = new char[] { 'A', 'B', 'C', 'D', 'E', 'F' };

// calculate e*n! (int)Math.Floor(Math.E * Math.Factorial(Letters.Length))
int x = 0;
for (int i = 1; i <= Letters.Length; i++)
    x = (x + 1) * i;

for (int i = 1; x > 0; i++)
{
    string Word = BaseX(i, Letters.Length, Letters);
    if (NoRepeat(Word))
    {
        Console.WriteLine(Word);
        x--;
    }
}

BaseX returns the string representation of Value for the given Base and specified Symbols:

string BaseX(int Value, int Base, char[] Symbols)
{
    StringBuilder s = new StringBuilder();

    while (Value > Base)
    {
        s.Insert(0, Symbols[Value % Base]);
        Value /= Base;
    }

    s.Insert(0, Symbols[Value - 1]);
    return s.ToString();
}

NoRepeat returns false if any letter occurs more than once:

bool NoRepeat(string s)
{
    bool[] Test = new bool[256];

    foreach (char c in s)
        if (Test[(byte)c])
            return false;
        else
            Test[(byte)c] = true;

    return true;
}

1. Sort the string in alphabet order. Say ABCDEF (your example)
2. Prepare a map between index and character

map[0] = 'A'; map[1] = 'B'; ... map[5] = 'F'

3 . Now your job is a lot more simple: find all combinations of number in which the later number is larger than the former

Combination(6,3):

for (int i = 0; i < 6 - 2; i++)
    for (int j = i + 1; j < 6 - 1; j++)
        for (int k = j + 1; k < 6; k++)
        {
            string strComb = map[i] + map[j] + map[k];
        }

This is mainly the idea, you could improve in your own way.

Contact me if you want more detail!

You can use this:

static List<string> list = new List<string>();
static string letters = "bcdehijkmnopqrstuvwxyz";
static void Combine(string combinatory)
{
    if(combinatory.Length < letters.Length)
    {
        Parallel.ForEach(letters, l =>
        {
            if (!combinatory.Contains(l)) Combine(combinatory + l);
        }); 
    } else
    {
        list.Add(combinatory);
        Console.WriteLine(combinatory);
    }
}

It will add to the list List all the possible combinations.

Then you can use the Sort() method in order to sort the list.