Sign in to follow this  

Listing all the n-permutations

This topic is 1971 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi everyone:

Considerer the problem to listing all the size-n permutations. I'm looking for something that works kinda this:

permutations(3) = [ (1,2,3) , (1,3,2) , (3,1,2) , (3,2,1) , (2,3,1) , (2,1,3) ]
NOTE: I don't care the order of the permutations (Despite of previous was ordenated by Johnson-Trotter criteria)

Actually, i've done two Python implementations:
- One of them builds from step i the step i+1 of a permutations, inserting the element i in each position of step i-permutation

[source lang="python"]def simplePerms(n):
n=n-2
conjPermAct = [ [1,2],[2,1] ]
for c in range(0,n):
conjPermSig=[]
for p in conjPermAct:
tamP = len(p)
for i in range(0,tamP+1):
auxp = p[:]
auxp.insert(i,tamP+1)
conjPermSig.append(auxp);
conjPermAct=conjPermSig

#print conjPermAct
print("Cantidad de permutaciones: %d" % len(conjPermAct))[/source]

-Next one is an implementation of the Johnson-Trotter algorithm (This gave me the best results):

[source lang="java"]def swap(list, i, j):
aux = list[i]
list[i] = list[j]
list[j] = aux

def permSJT(n):
perms = []
plist = [i for i in range(0,n)]
rlist = [True for i in range(0,n)]
permutationsEnd = False
while(not permutationsEnd):

#Find the maximum movile element
foundMobile = False
mobilesCand = plist[:]
actCand = 0
iActCand = 0
exchangeDir = 0
while(not foundMobile):
if(len(mobilesCand)==0):
permutationsEnd = True
break
else:
actCand = max(mobilesCand)
iActCand = plist.index(actCand)
if(rlist[actCand]):
if(iActCand-1 >= 0 and plist[iActCand-1] < plist[iActCand]):
foundMobile = True
exchangeDir = iActCand -1
else:
mobilesCand.remove(actCand)
rlist[actCand] = False
elif(not rlist[actCand]):
if(iActCand +1 < n and plist[iActCand] > plist[iActCand+1]):
foundMobile = True
exchangeDir = iActCand + 1
else:
mobilesCand.remove(actCand)
rlist[actCand] = True

#Exchange positions
swap(plist, iActCand, exchangeDir)

perms.append(plist)

#print perms
print("Number of permutations: %d" % len(perms))
[/source]
I supossed that JT algorithm was faster because it computes only the permutation needed, whereas "simplePerms" always computes the previous n-1 permutations to reach to the n-permutation ; however, the first one ("simplePerms") advantages it by several seconds (n>10 is notably better). There are two posibilities:
- "simplePerms" did less efforts than "JT Algorithm" (means the insertions are simpler?)
- My JT implementation is inefficient.

I'll apreciate your advices.
Thank you.

Share this post


Link to post
Share on other sites
The best algorithm that I have found for generating all permutations is the 'B.R. Heap's method'. It is described by Knuth in his [url="http://webcache.googleusercontent.com/search?q=cache:0zIFjphx-qsJ:www-cs-faculty.stanford.edu/~uno/fasc2b.ps.gz"]TAOCP book, vol 2B[/url]. See page 15 (the big page numbers on the left) for "Algorithm G", then see a mod to algorithm G on page 17 stating "The best is probably to let ... as suggested by B. R. Heap.". This algorithm utilizes an auxiliary data structure, and at each step makes only a single transposition of the elements, and a constant amount of work, to generate the next unvisited permutation. The traversal also has a nice property that one can skip past unwanted permutation prefixes if necessary.

Share this post


Link to post
Share on other sites

This topic is 1971 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this