Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Python (http://www.velocityreviews.com/forums/f43-python.html)
-   -   Writing Donald E. Knuth based code in Python, cont'd (http://www.velocityreviews.com/forums/t954443-writing-donald-e-knuth-based-code-in-python-contd.html)

 Juhani Ylikoski 11-12-2012 09:02 PM

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

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

 Vincent Vande Vyvre 11-12-2012 10:01 PM

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

Le 12/11/12 22:02, Juhani Ylikoski a écrit :
> 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.
>
>
> ---
>
>
> yours sincerely, Antti J Ylikoski
> Helsinki, Finland
> PhD student in the Aalto University
>

Thanks,

One comment in:

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

append() return None and self.app is no longer used in the code.

Missing something ?

--
Vincent V.V.

 Juhani Ylikoski 11-13-2012 07:52 AM

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

There were there two (2) bugs in the code that I posted. Thanks anyway.

A. J. Y.

"Vincent Vande Vyvre" kirjoitti
viestissä:mailman.3596.1352758176.27098.python-list@python.org...

Le 12/11/12 22:02, Juhani Ylikoski a écrit :
> 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.
>
>
> ---
>
>
> yours sincerely, Antti J Ylikoski
> Helsinki, Finland
> PhD student in the Aalto University
>

Thanks,

One comment in:

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

append() return None and self.app is no longer used in the code.

Missing something ?

--
Vincent V.V.

 All times are GMT. The time now is 07:36 PM.