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
...
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.