Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Writing Donald E. Knuth based code in Python, cont'd

Reply
Thread Tools

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

 
 
Juhani Ylikoski
Guest
Posts: n/a
 
      11-12-2012
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

 
Reply With Quote
 
 
 
 
Vincent Vande Vyvre
Guest
Posts: n/a
 
      11-12-2012
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.
Oqapy <https://launchpad.net/oqapy> . Qarte
<https://launchpad.net/qarte> . PaQager <https://launchpad.net/paqager>
 
Reply With Quote
 
 
 
 
Juhani Ylikoski
Guest
Posts: n/a
 
      11-13-2012
There were there two (2) bugs in the code that I posted. Thanks anyway.

A. J. Y.

"Vincent Vande Vyvre" kirjoitti
viestissä:(E-Mail Removed)...

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.
Oqapy <https://launchpad.net/oqapy> . Qarte
<https://launchpad.net/qarte> . PaQager <https://launchpad.net/paqager>

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Donald E. Knuth in Python, cont'd Antti J Ylikoski Python 6 04-16-2012 07:53 PM
Thank you Mr. Donald J. Trump Ministries In Faith Java 0 07-11-2009 07:05 PM
DONALD DUCK LOVES THE 40D! Annika1980 Digital Photography 2 05-01-2008 09:05 PM
Interview with Donald Knuth Lawrence D'Oliveiro NZ Computing 2 04-29-2008 11:16 AM
OT: knuth Noah Roberts C++ 4 09-28-2003 06:12 PM



Advertisments