1

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?

Improve this question
2
  • @jimifiki, i've reformulated my question. Is it clear now? Commented Jan 13, 2012 at 14:21
  • @Saul_Tigh: I've had a look at the Permutohedron, and I'm still convinced that, at least, itertools.permutations gives you a proper hint as to how to approach the problem. It won't give you the answer in the exact format you want, but every order of Permutohedron is the same as taking the permutation (n!). Since this is an academic exercise, it's wise to take what information you've received and attempt to apply it to your problem. Commented Jan 13, 2012 at 14:33

5 Answers 5

Reset to default
2

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]
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

your answer is much shotter, then the answer above yours. but they do the same thing. thank you.
2

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
Improve this answer

3 Comments

itertools is the only sane way to deal with problems like this.
I agree, although this doesn't deal with the "fixing the position of the xx element" that OP was asking about (whenever they do clarify their examples).
yes, i know, but i need to deal this problem without itertools in the way, I've described.
1

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.

Improve this answer

1 Comment

you're welcome, if you want [1,2,3,4] instead, You just have to do "A=perm(range(1,N+1),"",N-1)"
1

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.

Improve this answer

1 Comment

The second and third permutations in your output, (1, 2, 4, 3) and (1, 3, 2, 4), differ by a 3-cycle. The point in using Steinhaus-Johnson-Trotter is to get an ordering of the permutations where each transition is a 2-cycle (a swap).
0

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.