Breaking Down & Rearranging String into all possible combinations

Question

I want to break down and 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!

See: http://stackoverflow.com/questions/999050/most-elegant-way-to-get-all-subsets-of-an-array-in-c — Anthony Pegram, Jul 08 '11 at 03:14
I'm making a scrabble like game for my Software Major Project. I can search for a word in dictionary. eg. searching for "ABDE" i will get BEAD, BADE, ABED. However I would like to input a 6 letter word and get all combinations within it as well — Tony Wu, Jul 08 '11 at 03:14
I had a similar problem, maybe try taking your dictionary and putting it into a format that doesn't matter what order the characters are in (maybe alphabetically organize the letters in each word, then put letter counts after each unique letter). Then you just format the search the same way. — Jess, Jul 08 '11 at 03:16
Yea that's what i have; BEAD, BADE, ABED all have a common index "ABDE". However what i mean is getting search_string: "ABDE" to output 4 letter words, 3 letter words, 2 letter words as well. eg. BEAD, BADE, ABED, BED, DAB, BAD, etc. — Tony Wu, Jul 08 '11 at 03:24
@Tony: if your index is the sorted list of letters, you do not need to lookup all possible orders, just all unique sorted sets of letters, e.g. ABCD, ACDE, ABDE, ABCE, ABCDE. — Mark Elliot, Jul 08 '11 at 03:41
Seems like the sort of problem you could solve with recursion. — Cortright, Jul 08 '11 at 03:34
If this is a school project you should really tag it as homework. — gatkin, Jul 08 '11 at 17:21

gatkin · Accepted Answer · 2011-07-08T05:09:07.983

4

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.

edited Jul 08 '11 at 05:09

answered Jul 08 '11 at 03:20

gatkin

1,902
12
12

Scrabble is a case of permutations not combinations. There are e*n! results not 2^n-1 as suggested here. The naive solution is straight forward and perfectly tractable for the problem size (7 letters) and has the benefit of returning the results in alphabetic order which is something the OP asked for. – gordy Jul 09 '11 at 17:45
@Gordy: The OP's comments after his question explain that he has a dictionary indexed by sorted letter sequences, so he can look up ABDE and get the list BEAD, BADE, ABED. Given that, he doesn't actually need to permute anything (which I hadn't realized when I wrote my answer) so he doesn't have a n! problem. He was apparently stuck finding subsets of the available letters, in order to form shorter words. – gatkin Jul 09 '11 at 18:45
@Gordy: I confess I hadn't noticed the OP specified a maximum input string length. You're right, that makes a big difference. – gatkin Jul 09 '11 at 18:51

score 2 · Answer 2 · answered Jul 08 '11 at 04:01

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.

gordy · Answer 3 · 2011-07-09T07:42:12.860

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

longbkit · Answer 4 · 2011-07-08T03:44:21.967

Sort the string in alphabet order. Say ABCDEF (your example)
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!

score 0 · Answer 5 · edited Jun 04 '21 at 14:37

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.

Breaking Down & Rearranging String into all possible combinations

5 Answers5