Programming D. E. Knuth in Python with the Deterministic Finite Automaton construct

[Antti J Ylikoski]

In his legendary book series The Art of Computer Programming,
Professor Donald E. Knuth presents many of his algorithms in the form
that they have been divided in several individual phases, with
instructions to GOTO to another phase interspersed in the text of the
individual phases.



I. e. they look like the following, purely invented, example:  (Knuth is 
being clearer than me below.....)



A1.  (Do the work of Phase A1.)  If <zap> then go to Phase A5,
otherwise continue.

A2.  (Do some work.) If <zorp> go to Phase A4.

A3.  (Some more work.)

A4.  (Do something.)  If <condition ZZZ> go to Phase A1.

A5.  (Something more).  If <foobar> then go to Phase A2, otherwise
end.



I came across the problem, which would be the clearest way to program
such algorithms with a programming language such as Python, which has
no GOTO statement.  It struck me that the above construction actually
is a modified Deterministic Finite Automaton with states A1 -- A5 +
[END], transferring to different states, not on read input, but
according to conditions in the running program.

So one very clear way to program Knuth with Python is the following
kind of a construct.



continueLoop = 1
nextState = "A1"

while continueLoop:
     if nextState == "A1":
         # (Do the work of Phase A1.)
         if <zap>:
       	   nextState = "A5"
     elif nextState == "A2":
          # (Do some work.)
	 if zorp:
	    nextState = "A4"
	 else:
	    nextState = "A3"
     elif nextState == "A3":
         # (Some more work.)
	nextState = "A4"
     elif nextState == "A4":
         # (Do something.)
	if ZZZ:
	    nextState = "A1"
	else:
	    nextState = "A5"
     elif nextState == "A5":
         # (Something more).
	if foobar:
	    nextState = "A2"
	else:
	    continueLoop = 0
     else:
         error("Impossible -- I quit!\n")



Following is a working Python function which iteratively calculates
the lexicographically ordered permutations of integers [1, 2, 3, 4,
..., n], where n is an arbitary integer.  The function was written
after D. E. Knuth with the abovementioned DFA construct.




def iterAllPerm(n):

     # 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.  See pp. 39--40.

     listofPerm = [] # list of lists to collect permutations
     continueLoop = 1 # indicates whether to continue the iteration
     nextStat = "L1" # next phase in Knuth's text
     a = list(range(0, n+1)) # [0, 1, 2, 3, 4, ..., n] -- see Knuth

     while continueLoop:
         if nextStat == "L1":
             app = listofPerm.append(a[1:n+1])
             nextStat = "L2"
             continueLoop = 1
         elif nextStat == "L2":
             j = n - 1
             while a[j] >= a[j+1]:
                 j -= 1
             if j == 0:
                 continueLoop = 0
                 nextStat = "Finis Algorithm"
             else:
                 continueLoop = 1
                 nextStat = "L3"
         elif nextStat == "L3":
             l = n
             while a[j] >= a[l]:
                 l -= 1
             temp = a[j]
             a[j] = a[l]
             a[l] = temp
             nextStat = "L4"
             continueLoop = 1
         elif nextStat == "L4":
             k = j + 1
             l = n
             while k < l:
                 temp = a[k]
                 a[k] = a[l]
                 a[l] = temp
                 k += 1
                 l -= 1
             nextStat = "L1"
             continueLoop = 1
         else:
             continueLoop = 0
             error("Impossible -- I quit!\n")

     return(listofPerm)




kind regards, Antti J Ylikoski
Helsinki, Finland, the EU