Writing Donald E. Knuth based code in Python, cont'd

[Juhani Ylikoski]

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