2

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.

Improve this question
3
  • This is a permutations problem right? Commented Jan 29, 2012 at 1:38
  • 1
    Should we add a "homework" tag? Commented Jan 29, 2012 at 1:42
  • Startlingly similar to this question asked at nearly the same time. Commented Jan 29, 2012 at 20:59

4 Answers 4

Reset to default
3

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);     
}
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

This is a bitwise and operation in C, C++, C#, and Java (though in the last two you need to add m & 1 != 0 to compile). It means "if the binary representation of m contains 1 in the least significant bit position". m & 2 means the second least significant bit; m & 4 is third, and so on, continuing with the powers of 2.
Sorry, but I still don't quite understand. m is the count, is that what I'm supposed to be comparing?
@Lolcoder m is a "bit mask". It goes 0 through 7, or 000, 001, 010, 011, 100, 101, 110, 111 in binary. 1 is 001, 2 is 010, and 4 is 100 in binary. Hence the first comma will appear only in odd numbers 1, 3, 5, and 7; the second comma will be in 2, 3, 6, and 7; the third one will be in 4, 5, 6, and 7. I just edited the code to make it proper C#. Step through it in a debugger to see how it works.
Thanks, I understand the bit mask part. How did you come up with comparing to 1, 2 and 4? If I want to automate this for a varied length of string. How can I know what number to compare the bit mask to and the amount of times to loop? I'm thinking loopCount = 2^stringArray.Count.
@Lolcoder use the left shift: 1 is 1<<0, 2 is 1<<1, 4 is 1<<2, 8 is 1<<3, and so on. You would run a loop on i, checking if ((m & (1<<i)) != 0).
1

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.

Improve this answer

1 Comment

could you give a sample output in order of how it would be generated please?
0

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.

Improve this answer

Comments

0

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.

Improve this answer

2 Comments

They still need to be the same order. so a cannot move from index 1.
@Lolcoder, my suggested code does not change the order of the strings. In fact, I make sure they are alphabetically sorted using str.OrderBy(s=>s).ToList(). Of course, you may or may not need this line.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.