Permutation of a list of strings algorithm

Question

I need help understanding how to write a permutation algorithm. (if this is even permutation, they have to be in order and use the same values).

List<string> str = new List<string>{"a", "b", "c", "d"};

How can I get a list of each permutation available in this list? For eg.

1. a, b, c, d
2. ab, c, d
3. ab, cd
4. abc, d
5. abcd
6. a, bc, d
7. a, bcd
8. a, b, cd

For some reason I cant find a pattern to start with. I'd also like to be able to disregard permutation when a joined string has a count of like X characters. So if X was 4, in that list, number 5 wouldn't exist and there would be 7 permutations.

private List<string> permute(List<string> values, int maxPermutation)
{
     //alittle help on starting it would be great :)
}

I looked and read this, but he does not keep the order.

Answer 1

This is rather straightforward: you have three spots where you could either put a comma or to put nothing. There are eight combinations corresponding to 2^3 binary numbers.

For each number from 0 to 7, inclusive, produce a binary representation. Put a comma in each position where binary representation has 1; do not put comma where there's zero.

for (int m = 0 ; m != 8 ; m++) {
    string s = "a";
    if ((m & 1) != 0) s += ",";
    s += "b";
    if ((m & 2) != 0) s += ",";
    s += "c";
    if ((m & 4) != 0) s += ",";
    s += "d";
    Console.WriteLine(s);     
}

Answer 2

You could take a recursive approach: Take the first letter, build all possible combinations starting with the second one (this is the recursion...) and prepend the first letter to each of them. Then take the first two letters together, recursively build all combinations starting with the third one. And so on ...

As for you additional requirement: If you want to exclude all "combinations" containing a string with X letters, just skip this number when constructing the first string.

Answer 3

The Binary approach above is correct and this is actually a partitioning problem (but not "The Partitioning Problem") and not a permutation problem.

http://en.wikipedia.org/wiki/Partition_of_a_set

Watch out because of the number of partitions grows faster than exponentially (e^e^n) so it will be really slow for large strings.

Answer 4

Try the following code. I haven't tested it, but I think it's what you are looking for.

List<string> str = new List<string>{ "a", "h", "q", "z", "b", "d" };
List<List<string>> combinations = combine(str.OrderBy(s=>s).ToList());

List<List<string>> combine(List<string> items)
{
    List<List<string>> all = new List<List<string>>();

    // For each index item in the items array
    for(int i = 0; i < items.Length; i++)
    {
        // Create a new list of string
        List<string> newEntry = new List<string>();
        // Take first i items
        newEntry.AddRange(items.Take(i));
        // Concatenate the remaining items
        newEntry.Add(String.concat(items.Skip(i)));
        // Add these items to the main list
        all.Add(newEntry);

        // If this is not the last string in the list
        if(i + 1 < items.Length)
        {
            // Process sub-strings
            all.AddRange(combine(items.Skip(i + 1).ToList()));
        }
    }
    return all;
}

If you need to generate combinations (or permutations or variations), then Combinatorics is a fantastic library.