The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Message from discussion Writing Donald E. Knuth based code in Python, cont'd

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Nov 12 2012, 4:02 pm
Newsgroups: comp.lang.python
From: "Juhani Ylikoski" <antti.yliko...@elisanet.fi>
Date: Mon, 12 Nov 2012 23:02:36 +0200
Local: Mon, Nov 12 2012 4:02 pm
Subject: Writing Donald E. Knuth based code in Python, cont'd
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

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