About
While working on a toy software for computing association rules out of a given database, I ended up working on a few different algorithms for computing permutation on lists. The following Python snippets are a result of this research.
Permutations
The original algorithm is a fast non-recursive Python generator which computes every possible arrangement of a list of elements, also known as permutations.
Being a non-recursive generator means that it only generates one item at a time and returns it to the caller, rather than building all possibilities in memory before returning the result.
1 def permutation(lst):
2 queue = [-1]
3 lenlst = len(lst)
4 while queue:
5 i = queue[-1]+1
6 if i == lenlst:
7 queue.pop()
8 elif i not in queue:
9 queue[-1] = i
10 if len(queue) == lenlst:
11 yield [lst[j] for j in queue]
12 queue.append(-1)
13 else:
14 queue[-1] = i
The total number of permutations of a set of N elements is given by N! (factorial of N). As an example, there are 120 different ways to order 5 elements.
Derangements
An interesting aspect of the algorithm above is that it may be easily adapted to compute derangements, which are a special set of permutations which do not allow any member of the given list to be in its initial position. For instance, the only derangements of the [1, 2, 3] list are [2, 3, 1] and [3, 1, 2].
Here is the same algorithm modified to build derangements:
1 def derangement(lst):
2 queue = [-1]
3 lenlst = len(lst)
4 while queue:
5 i = queue[-1]+1
6 if i == lenlst:
7 queue.pop()
8 elif i not in queue and i != len(queue)-1:
9 queue[-1] = i
10 if len(queue) == lenlst:
11 yield [lst[x] for x in queue]
12 queue.append(-1)
13 else:
14 queue[-1] = i
Another curiosity is that while the total number of permutations of a set of N elements is given by N! (factorial of N), the number of derangements of a set of N elements is given by !N (subfactorial of N), which has a very good approximation as N!/e (factorial of N divided by e). As an example, while the total number of permutations of 5 elements is 120, the total number of derangements is 44 (120/2.718 == 44.150).
Permutations of all subsets
The following algorithm has a small change when compared to the algorithms presented above, and is indeed the original intent when these algorithms were born.
This version will compute not only all permutations of the given list, but also all the permutations of all the k-subsets of that list.
1 def kpermutation(lst):
2 queue = [-1]
3 lenlst = len(lst)
4 while queue:
5 i = queue[-1]+1
6 if i == lenlst:
7 queue.pop()
8 elif i not in queue:
9 queue[-1] = i
10 yield [lst[j] for j in queue]
11 queue.append(-1)
12 else:
13 queue[-1] = i
Notice that the only change needed is removing the constraint on the queue size before yielding the next value.
For the list [1, 2, 3], this function will generate the following combinations:
1 [[1], [1, 2], [1, 2, 3], [1, 3], [1, 3, 2],
2 [2], [2, 1], [2, 1, 3], [2, 3], [2, 3, 1],
3 [3], [3, 1], [3, 1, 2], [3, 2], [3, 2, 1]]
Computing the total number of combinations that this function will produce is an interesting task. We know that all permutations of N elements is given by N! (factorial of N). We also know that besides computing all permutations of the full set, it will also compute the permutations of all contained subsets. The number of ways that N elements may be represented as a subset of S elements is given by the binomial coefficient, which is computed by N!/((N-S)!*S!). In Python, it becomes:
1 def f(x):
2 return x <= 1 or f(x-1)*x
3
4 def binomial_coefficient(n, i):
5 return f(n)/(f(n-i)*f(i))
Now that we know how to compute the number of subsets, and the number of combinations of each subset, computing the total number of combinations of the above function is trivial, by multiplying each other:
1 def total_kpermutations(n):
2 t = 0
3 fn = f(n)
4 for i in range(1,n+1):
5 fi = f(i)
6 t += fi*(fn/(f(n-i)*fi))
7 return t
As an example, while the traditional number of permutations of 5 elements is 120, with the new function the same elements will yield 325 different values.
All combinations of N elements
A slightly different task is computing all combinations of N elements over K positions, given that 1 <= K <= N, and elements may repeat. Adapting the presented algorithm to compute these ordered sets is pretty easy:
1 def allcombinations(lst):
2 queue = [-1]
3 lenlst = len(lst)
4 while queue:
5 i = queue[-1]+1
6 if i == lenlst:
7 queue.pop()
8 else:
9 queue[-1] = i
10 yield [lst[j] for j in queue]
11 if len(queue) < lenlst:
12 queue.append(-1)
This will generate the following output for the [1, 2, 3] list:
1 [[1], [1, 1], [1, 1, 1], [1, 1, 2], [1, 1, 3],
2 [1, 2], [1, 2, 1], [1, 2, 2], [1, 2, 3],
3 [1, 3], [1, 3, 1], [1, 3, 2], [1, 3, 3],
4 [2], [2, 1], [2, 1, 1], [2, 1, 2], [2, 1, 3],
5 [2, 2], [2, 2, 1], [2, 2, 2], [2, 2, 3],
6 [2, 3], [2, 3, 1], [2, 3, 2], [2, 3, 3],
7 [3], [3, 1], [3, 1, 1], [3, 1, 2], [3, 1, 3],
8 [3, 2], [3, 2, 1], [3, 2, 2], [3, 2, 3],
9 [3, 3], [3, 3, 1], [3, 3, 2], [3, 3, 3]]
Computing the number of generated outputs is easy as well. We know that each position will present every element once, so for K positions, N elements will be presented in N^K ways. In our case 1 <= K <= N, so the Python function for that is:
1 def total(n):
2 return sum(n**i for i in range(1,n+1))
For example, 5 elements will yield 3905 different values!