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

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.