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

Discussion in 'Python' started by Juhani Ylikoski, Nov 12, 2012.

  1. 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
    Juhani Ylikoski, Nov 12, 2012
    #1
    1. Advertising

  2. 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>
    Vincent Vande Vyvre, Nov 12, 2012
    #2
    1. Advertising

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

    A. J. Y.

    "Vincent Vande Vyvre" kirjoitti
    viestissä:...

    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>
    Juhani Ylikoski, Nov 13, 2012
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. gelbeiche
    Replies:
    6
    Views:
    426
    CrayzeeWulf
    Apr 25, 2005
  2. KyoGaSuki
    Replies:
    5
    Views:
    336
  3. Ministries In Faith

    Thank you Mr. Donald J. Trump

    Ministries In Faith, Jul 11, 2009, in forum: Java
    Replies:
    0
    Views:
    302
    Ministries In Faith
    Jul 11, 2009
  4. Antti J Ylikoski
    Replies:
    12
    Views:
    316
    Dennis Lee Bieber
    Mar 19, 2012
  5. Antti J Ylikoski

    Donald E. Knuth in Python, cont'd

    Antti J Ylikoski, Apr 11, 2012, in forum: Python
    Replies:
    6
    Views:
    652
    Tim Daneliuk
    Apr 16, 2012
Loading...

Share This Page