0

I have a list of letters, this is just an example list:

['a','b','c','d','e']

How do I compute every combination of the list? The letters cannot repeat, for example.

a,b,c,d,e
a,c,b,d,e
a,c,d,b,e
a,c,d,e,b
a,e,d,c,b
...

closed as off-topic by Robert Harvey, GlenH7, Michael Kohne, thorsten müller, gnat Oct 6 '13 at 6:19

  • This question does not appear to be about software engineering within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • itertools.permutations – Simeon Visser Oct 5 '13 at 0:28
  • 2
    itertools.permutations – fjarri Oct 5 '13 at 0:28
  • 1
    This question should be closed/moved to SO, not answered (which does not mean I can't help OP with a short comment). – fjarri Oct 5 '13 at 1:35
  • 4
    This question appears to be off-topic because it is about implementation issues, but it lacks prior research, and so is unsuitable on Stack Overflow. – Robert Harvey Oct 5 '13 at 1:40
  • 1
    On the other hand, if you want to know how the solution works, you should read the classics: Section 7.2.1.2 of The Art of Computer Programming (www-cs-faculty.stanford.edu/~uno/fasc2b.ps.gz‎) details exactly that. – Kilian Foth Oct 5 '13 at 8:11
6

The simple answer for Python is the itertools library. That's it, you're done with it.

In Ruby, it's part of the Array class.

$ irb
>> a = [1, 2, 3]
=> [1, 2, 3]
>> a.permutation.to_a
=> [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

However, this is a very boring answer and doesn't help anyone who (despite the tag and me pointing to other languages too) is trying to find out how to create every permutation of a set.

The basic approach to this you iterate over each item in the set, and generate the permutations of all of the remaining set.

The simple approach to this is a backtracking model. The method do() does whatever one wants to do, be it print out or calculate with it further.

exchange (x, y) {
    return y, x;
}
generate (n) {
    int c;
    if(n = 1) do();
    for (c = 1; c < n; c++)
        {  exchange(c,n); generate(n-1); exchange(c,n); }
}

This algorithm does 2n! exchanges.

Heap's method is a simple recursive approach. Consider the following

-*-*-*-*-*-
 | | | | | 
-*-|-*-|-*-
   |   |  
---*---*---
a b c a b c
b a a c c b
c c b b a a

You start out with abc, and then swap 1 and 2, then 1, 3, then 1, 2, then 1, 3, then 1, 2. If you have 4 elements, after this sequence of pattern is completed you swap 1, 4 - then another sequence and 2, 4, and another sequence and 3, 4.

If it was 5, then you'd repeat the sequence of 4, and then do 1, 5, then 2, 5, then 3, 5. You should get the idea.

Writing this recursively is rather straight forward.

generate(n) {
    int c;
    if (n == 1) { do(); return; }
    for (c = 1; c <= n; c++) {
        generate(n-1);
        exchange(n % 2 ? 1 : c, n)
    }
}

If you really want to read more about this, The Art of Computer Programming Volume 4, Combinatorial Algorithms, section 7.2.1.2 is titled "Generating All Permutations" that goes deeply into the math.

Not the answer you're looking for? Browse other questions tagged or ask your own question.