The old Google Groups will be going away soon, but your browser is incompatible with the new version.
This is a Usenet group - learn more
Writing Donald E. Knuth based code in Python, cont'd
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 3 messages
The group you are posting to is a Usenet group. Messages posted to this group will make your email address visible to anyone on the Internet.
Your reply message has not been sent.
Your post was successful

From:
To:
Cc:
Followup To:
 Add Cc | Add Followup-to | Edit Subject
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Nov 12 2012, 4:02 pm
Newsgroups: comp.lang.python
From: "Juhani Ylikoski" <antti.yliko...@elisanet.fi>
Date: Mon, 12 Nov 2012 23:02:36 +0200
Local: Mon, Nov 12 2012 4:02 pm
Subject: 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

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

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Nov 12 2012, 5:09 pm
Newsgroups: comp.lang.python
From: Vincent Vande Vyvre <vincent.vandevy...@swing.be>
Date: Mon, 12 Nov 2012 23:01:56 +0100
Local: Mon, Nov 12 2012 5:01 pm
Subject: Re: Writing Donald E. Knuth based code in Python, cont'd
Le 12/11/12 22:02, Juhani Ylikoski a écrit :

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

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Nov 13 2012, 2:52 am
Newsgroups: comp.lang.python
From: "Juhani Ylikoski" <antti.yliko...@elisanet.fi>
Date: Tue, 13 Nov 2012 09:52:34 +0200
Local: Tues, Nov 13 2012 2:52 am
Subject: 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-l...@python.org...

Le 12/11/12 22:02, Juhani Ylikoski a crit :

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