So I encountered a problem of permutations with fixed previous element in list. So, I have list, which is an ordered sequence of numbers from 1 till n.
EDIT
here's a reformuliration of my question:
Can you imagine a tree graph? So, 1st level - it's a top (also known as parent) vertex. So, if we have vertex like [1, 2, 3, 4], our next step would be to make permutations, inserting all numbers in the position n, it means that in output we would have this:
1.1 lvl [1, 2, 3, 4]
2.1 lvl [1, 2, 4, 3]
3.1 lvl [1, 3, 4, 2]
4.1 lvl [2, 3, 4, 1]
So, then we look at level 1.1 and make permutations of n-1th element ( 4 is fixed and do not take part in permutation on this level). Output would be:
1.1.1 lvl [1, 2, 3, 4]
1.1.2 lvl [1, 3, 2, 4]
1.1.3 lvl [2, 3, 1, 4]
The we took 1.1.1 lvl and fix n-2 element (as you can see there is no point to fix 1st element). So, on this level we have fixed 3, and 4, which is n-1th and nth elemets, outut is:
1.1.1.1 lvl [1, 2, 3, 4]
1.1.1.2 lvl [2, 1, 3, 4]
We have dinished here, but do not have finish yet. Go on lvl up ( it's level 1.1.2). And permutate it. Here we have fixed n-1th element (it's 2) and nth (it's 4)
1.1.2.1 lvl [1, 3, 2, 4]
1.1.2.2 lvl [3, 1, 2, 4]
Finished here. GOTO on upper level. Here fixed 1 and 4. So,
1.1.3.1 lvl [2, 3, 1, 4]
1.1.3.2 lvl [3, 2, 1, 4]
We have finished the level 1.1 and going to 2.1, where we repeat the same procedure.
So, the question is: how to do this in python?
The permutations in your results all differ from the previous element by swapping two elements.
Swapping two elements corresponds to an edge in a permutohedron.
This suggests that you are trying to visit the vertices in the permutohedron according to some criteria. Can you explain what the criteria is in geometric terms?
For example, one possible question is how to generate all possible permutations by swapping just two elements at each turn. This corresponds to finding a Hamiltonian path on the permutohedron. The answer to this question is given by the Steinhaus-Johnson-Trotter algorithm which gives an O(n) method for finding the next permutation from a given position.
EDIT
Here is some Python code for the updated question:
def perms(A):
if len(A)==1:
yield A
for i in xrange(len(A)-1,-1,-1):
for B in perms(A[:i]+A[i+1:]):
yield B+A[i:i+1]
Running
for a in perms([1,2,3,4]):
print a
prints the following:
[1, 2, 3, 4]
[2, 1, 3, 4]
[1, 3, 2, 4]
[3, 1, 2, 4]
[2, 3, 1, 4]
[3, 2, 1, 4]
[1, 2, 4, 3]
[2, 1, 4, 3]
[1, 4, 2, 3]
[4, 1, 2, 3]
[2, 4, 1, 3]
[4, 2, 1, 3]
[1, 3, 4, 2]
[3, 1, 4, 2]
[1, 4, 3, 2]
[4, 1, 3, 2]
[3, 4, 1, 2]
[4, 3, 1, 2]
[2, 3, 4, 1]
[3, 2, 4, 1]
[2, 4, 3, 1]
[4, 2, 3, 1]
[3, 4, 2, 1]
[4, 3, 2, 1]
You could always use itertools.permutations.
from itertools import permutations
perm = permutations([1, 2, 3, 4])
while True:
try:
print perm.next() # perm.next() gives a tuple of the next permutation
except StopIteration:
break
I hope this is what you wanted: I preferred to use indeces 0,1,2,3 instead of 1,2,3,4
def switch(a,b,c):
aux = a[b]
a[b] = a[c]
a[c] = aux
class perm():
def __init__(self,mylist,txt,myreference,flag = None):
self.mylist = []
self.mylist.extend(mylist)
self.myreference = myreference
self.txt = txt
if flag == None:
print self.mylist,txt
def make_perm(self):
count = 0
if self.myreference > 1:
New = perm(self.mylist,self.txt+str(count),self.myreference-1,0)
New.make_perm()
for i in xrange(self.myreference-1,-1,-1):
switch(self.mylist,i,self.myreference)
count += 1
New = perm(self.mylist,self.txt+str(count),self.myreference-1)
New.make_perm()
N = 4
A = perm(range(N),"",N-1)
A.make_perm()
I hope yo realize that once we are on [1, 2, 4, 3] and we fix the 3 in the 4th position one cannot go on 1,4,2,3 moving on the permutohedron without modifying the position of 3.
If standard library solution is not suitable for some reason, I can advice to make a recursive function, which deals with the permutations.
Hinting on the solution:
def perm(lst):
if len(lst) == 1: # single element list
return [lst]
res = []
for last_item in lst:
lst1 = filter(lambda x: x!= last_item, lst) # ... without last_item
for p in perm(lst1):
res.append(p + [last_item])
return res
I wanted the solution to be simple. There are ways to optimize it, use generators and lazy calculations, etc.
