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 -- http://mail.python.org/mailman/listinfo/python-list
