Permutations With Fixed Previous Element In Python

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 reformulirati

Solution 1:

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:

defperms(A):
    iflen(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]

Solution 2:

You could always use itertools.permutations.

from itertools import permutations
perm = permutations([1, 2, 3, 4])
whileTrue:
    try:
        print perm.next() # perm.next() gives a tuple of the next permutationexcept StopIteration:
        break

Solution 3:

I hope this is what you wanted: I preferred to use indeces 0,1,2,3 instead of 1,2,3,4

defswitch(a,b,c):
    aux = a[b]
    a[b] = a[c]
    a[c] = aux
classperm():
    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
    defmake_perm(self):
        count = 0if 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.

Solution 4:

Inspired by Peter de Rivaz's solution, we can also do it in this way.

import itertools as it
import numpy as np
for comb in it.combinations(np.arange(1,5), r=4):
    for comb_perm in it.permutations(comb, r=4):
        print(comb_perm)

This will lead to

(1, 2, 3, 4)
(1, 2, 4, 3)
(1, 3, 2, 4)
(1, 3, 4, 2)
(1, 4, 2, 3)
(1, 4, 3, 2)
(2, 1, 3, 4)
(2, 1, 4, 3)
(2, 3, 1, 4)
(2, 3, 4, 1)
(2, 4, 1, 3)
(2, 4, 3, 1)
(3, 1, 2, 4)
(3, 1, 4, 2)
(3, 2, 1, 4)
(3, 2, 4, 1)
(3, 4, 1, 2)
(3, 4, 2, 1)
(4, 1, 2, 3)
(4, 1, 3, 2)
(4, 2, 1, 3)
(4, 2, 3, 1)
(4, 3, 1, 2)
(4, 3, 2, 1)

I have tested the running time, 0.0029001235961914062, on my Fedora machine. Hope it can help.

Solution 5:

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:

defperm(lst):
   iflen(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.