Following comes a working, debugged Python program which computes the

permutations of the integers 1, 2, 3 - n after Donald E. Knuth. I

present it as an example of writing straightforward, easy Knuth-based

code in a language with no GOTO statement.

The Python program has been written after the DFA construct I

previously discussed in this newsgroup, and after Knuth's discussion

of the solution of the problem; and according the (very good)

discussions in this newsgroup. To my opinion, it no more is a "crow's

nest" as they say in Finnish.

This program was needed for a real problem, namely computing optimal

tournament tables for a Bughouse (Tandem) chess tournament. See

http://en.wikipedia.org/wiki/Bughouse_chess
Knuth became criticized in the newsgroup; but to my opinion his books

are still useful and nontrivially needed.

----------------------------------------------------------------------

class DFA(object):

# Iteratively generate all permutations of n integers 1-n.

# After Donald Knuth, The Art of Computer Programming, Vol4, Fascicle 2,

# ISBN 0-201-85393-0, on Pages 39-40.

def __init__(self, n):

self.n = n

self.listofPerm = [] # list of lists to collect permutations

self.nextStat = self.E1 # next phase in Knuth's text

self.a = list(range(0, n+1)) # [0, 1, 2, 3, 4, ..., n] -- see Knuth

def E1(self): # Phase 1 in Knuth's text

self.app = self.listofPerm.append(self.a[1:self.n+1])

return self.E2 # next state: E2

def E2(self): # Phase 2 in Knuth's text

self.j = self.n - 1

while self.a[self.j] >= self.a[self.j+1]:

self.j -= 1

if self.j == 0:

return None # algorithm finishes

else:

return self.E3 # next state: E3

def E3(self): # Phase 3 in Knuth

self.l = self.n

while self.a[self.j] >= self.a[self.l]:

self.l -= 1

self.temp = self.a[self.j]

self.a[self.j] = self.a[self.l]

self.a[self.l] = self.temp

return self.E4 # next state: E4

def E4(self): # Phase 4

self.k = self.j + 1

self.l = self.n

while self.k < self.l:

self.temp = self.a[self.k]

self.a[self.k] = self.a[self.l]

self.a[self.l] = self.temp

self.k += 1

self.l -= 1

return self.E1 # following phase: Phase 1

def runDFA(self):

self.nextState = self.E1

while self.nextState is not None:

self.nextState = self.nextState()

return(self.listofPerm)

----------------------------------------------------------------------

yours sincerely, Antti J Ylikoski

Helsinki, Finland

PhD student in the Aalto University