Jump to content
  • Advertisement
Sign in to follow this  

Listing all the n-permutations

This topic is 2256 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):
conjPermAct = [ [1,2],[2,1] ]
for c in range(0,n):
for p in conjPermAct:
tamP = len(p)
for i in range(0,tamP+1):
auxp = p[:]

#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
list = 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):
permutationsEnd = True
actCand = max(mobilesCand)
iActCand = plist.index(actCand)
if(iActCand-1 >= 0 and plist[iActCand-1] < plist[iActCand]):
foundMobile = True
exchangeDir = iActCand -1
rlist[actCand] = False
elif(not rlist[actCand]):
if(iActCand +1 < n and plist[iActCand] > plist[iActCand+1]):
foundMobile = True
exchangeDir = iActCand + 1
rlist[actCand] = True

#Exchange positions
swap(plist, iActCand, exchangeDir)


#print perms
print("Number of permutations: %d" % len(perms))
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 TAOCP book, vol 2B. 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
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!