Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Writing Donald E. Knuth based code in Python, cont'd
77 views
Skip to first unread message
Juhani Ylikoski
Nov 12, 2012, 4:02:36 PM11/12/12
to
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
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
Nov 12, 2012, 5:01:56 PM11/12/12
to pytho...@python.org
Le 12/11/12 22:02, Juhani Ylikoski a écrit :
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.
Oqapy <https://launchpad.net/oqapy> . Qarte
<https://launchpad.net/qarte> . PaQager <https://launchpad.net/paqager>
> 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.
>
>
> ---
>
>
> 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,
> Helsinki, Finland
> PhD student in the Aalto University
>
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
Missing something ?
--
Vincent V.V.
Oqapy <https://launchpad.net/oqapy> . Qarte
<https://launchpad.net/qarte> . PaQager <https://launchpad.net/paqager>
Juhani Ylikoski
Nov 13, 2012, 2:52:34 AM11/13/12
to
There were there two (2) bugs in the code that I posted. Thanks anyway.
A. J. Y.
"Vincent Vande Vyvre" kirjoitti
viestiss�:mailman.3596.1352758...@python.org...
Le 12/11/12 22:02, Juhani Ylikoski a �crit :
A. J. Y.
"Vincent Vande Vyvre" kirjoitti
viestiss�:mailman.3596.1352758...@python.org...
Le 12/11/12 22:02, Juhani Ylikoski a �crit :
0 new messages