# 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.

## 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
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
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.

Thank you.

##### 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.

1. 1
2. 2
3. 3
Rutin
18
4. 4
JoeJ
14
5. 5

• 14
• 10
• 23
• 9
• 32
• ### Forum Statistics

• Total Topics
632630
• Total Posts
3007521
• ### Who's Online (See full list)

There are no registered users currently online

×