Fast generation of permutations

Discussion in 'Python' started by =?ISO-8859-1?Q?Frode_=D8ijord?=, Jan 25, 2006.

  1. Hi all,
    given a sequence of n elements i need to generate all possible
    permutations of length k <= n.

    I found an elegant way to do this recursively:

    def comb(items, n):
    if n==0: yield []
    else:
    for i in xrange(len(items)):
    for cc in comb(items[i+1:],n-1):
    yield [items]+cc

    However, this is way too slow for my needs. I try to use this to
    generate all possible 5 card poker hands, but this takes around 17
    seconds on an Athlon 2200. That's a 2 orders of magnitude too slow for
    my needs.

    I am familiar with writing Python extensions in C++, but I will not do
    this until I am confident that it is the only way to get the speed I need.

    Any of you excellent sirs have any suggestions on how I can speed this up?

    Please find attached an example script that executes and times the poker
    hand generation.


    --
    Frode, SIM

    "Any fool can write code that a computer can understand.
    Good programmers write code that humans can understand"

    import sys
    from timeit import Timer

    def comb(items, n):
    if n==0: yield []
    else:
    for i in xrange(len(items)):
    for cc in comb(items[i+1:],n-1):
    yield [items]+cc


    def test():
    cards = range(52)
    for hand in comb(cards, 5):
    "do something with the hand"

    def main(argv):
    t = Timer("test()", "from __main__ import test")
    print t.timeit(1)


    if __name__=="__main__":
    sys.exit(main(sys.argv[1:]))
     
    =?ISO-8859-1?Q?Frode_=D8ijord?=, Jan 25, 2006
    #1
    1. Advertising

  2. On Wed, Jan 25, 2006 at 03:33:48PM +0100, Frode ?ijord wrote:
    > Hi all,
    > given a sequence of n elements i need to generate all possible
    > permutations of length k <= n.
    >
    > I found an elegant way to do this recursively:
    >
    > def comb(items, n):
    > if n==0: yield []
    > else:
    > for i in xrange(len(items)):
    > for cc in comb(items[i+1:],n-1):
    > yield [items]+cc
    >
    > However, this is way too slow for my needs. I try to use this to
    > generate all possible 5 card poker hands, but this takes around 17
    > seconds on an Athlon 2200. That's a 2 orders of magnitude too slow for
    > my needs.
    >
    > I am familiar with writing Python extensions in C++, but I will not do
    > this until I am confident that it is the only way to get the speed I need.
    >


    You might want to look at a specific purpose library for poker hands:
    http://pokersource.sourceforge.net/

    It has python bindings and is included in Debian based distributions
    as the 'pypoker-eval' package.

    If you really want to do combinations a C extension has already
    been written (by me).

    http://probstat.sourceforge.net/

    import probstat
    cards = range(52)
    for (hand) in probstat.Combination(card, 5):
    pass

    Takes 1.3 seconds on my laptop instead of 17 seconds for the pure
    python version which is only one order of magnitude faster.
    Creating and populating 2598960 list objects one at a time isn't free!

    for (i) in xrange(2598960):
    l = []

    Takes 0.8 seconds on the same machine.

    -jack
     
    Jack Diederich, Jan 25, 2006
    #2
    1. Advertising

  3. Frode Øijord schrieb:
    > Hi all,
    > given a sequence of n elements i need to generate all possible
    > permutations of length k <= n.
    >
    > I found an elegant way to do this recursively:
    >
    > def comb(items, n):
    > if n==0: yield []
    > else:
    > for i in xrange(len(items)):
    > for cc in comb(items[i+1:],n-1):
    > yield [items]+cc
    >
    > However, this is way too slow for my needs. I try to use this to
    > generate all possible 5 card poker hands, but this takes around 17
    > seconds on an Athlon 2200. That's a 2 orders of magnitude too slow for
    > my needs.
    >
    > I am familiar with writing Python extensions in C++, but I will not do
    > this until I am confident that it is the only way to get the speed I need.
    >
    > Any of you excellent sirs have any suggestions on how I can speed this up?
    >
    > Please find attached an example script that executes and times the poker
    > hand generation.
    >
    >
    >
    > ------------------------------------------------------------------------
    >
    > import sys
    > from timeit import Timer
    >
    > def comb(items, n):
    > if n==0: yield []
    > else:
    > for i in xrange(len(items)):
    > for cc in comb(items[i+1:],n-1):
    > yield [items]+cc
    >
    >
    > def test():
    > cards = range(52)
    > for hand in comb(cards, 5):
    > "do something with the hand"
    >
    > def main(argv):
    > t = Timer("test()", "from __main__ import test")
    > print t.timeit(1)
    >
    >
    > if __name__=="__main__":
    > sys.exit(main(sys.argv[1:]))


    If you don't need the flexibility of having the number of elements in
    your permutation as a parameter - as it seems to be the case in your
    poker example - simply use nested for-loops, 5 in this case.
    Example for 5 out of 7 (just to keep the output shorter):
    for i1 in range(7):
    for i2 in range(i1+1,7):
    for i3 in range(i2+1,7):
    for i4 in range(i3+1,7):
    for i5 in range(i4+1,7):
    print i1,i2,i3,i4,i5

    0 1 2 3 4
    0 1 2 3 5
    0 1 2 3 6
    0 1 2 4 5
    0 1 2 4 6
    0 1 2 5 6
    0 1 3 4 5
    0 1 3 4 6
    0 1 3 5 6
    0 1 4 5 6
    0 2 3 4 5
    0 2 3 4 6
    0 2 3 5 6
    0 2 4 5 6
    0 3 4 5 6
    1 2 3 4 5
    1 2 3 4 6
    1 2 3 5 6
    1 2 4 5 6
    1 3 4 5 6
    2 3 4 5 6

    Have fun
    Michael
     
    Michael Amrhein, Jan 25, 2006
    #3
  4. Michael Amrhein schrieb:
    > Frode Øijord schrieb:
    >> Hi all,
    >> given a sequence of n elements i need to generate all possible
    >> permutations of length k <= n.
    >>
    >> I found an elegant way to do this recursively:
    >>
    >> def comb(items, n):
    >> if n==0: yield []
    >> else:
    >> for i in xrange(len(items)):
    >> for cc in comb(items[i+1:],n-1):
    >> yield [items]+cc
    >>
    >> However, this is way too slow for my needs. I try to use this to
    >> generate all possible 5 card poker hands, but this takes around 17
    >> seconds on an Athlon 2200. That's a 2 orders of magnitude too slow for
    >> my needs.
    >>
    >> I am familiar with writing Python extensions in C++, but I will not do
    >> this until I am confident that it is the only way to get the speed I
    >> need.
    >>
    >> Any of you excellent sirs have any suggestions on how I can speed this
    >> up?
    >>
    >> Please find attached an example script that executes and times the
    >> poker hand generation.
    >>
    >>
    >>
    >> ------------------------------------------------------------------------
    >>
    >> import sys
    >> from timeit import Timer
    >>
    >> def comb(items, n):
    >> if n==0: yield []
    >> else:
    >> for i in xrange(len(items)):
    >> for cc in comb(items[i+1:],n-1):
    >> yield [items]+cc
    >>
    >>
    >> def test():
    >> cards = range(52)
    >> for hand in comb(cards, 5):
    >> "do something with the hand"
    >> def main(argv):
    >> t = Timer("test()", "from __main__ import test")
    >> print t.timeit(1)
    >>
    >>
    >> if __name__=="__main__":
    >> sys.exit(main(sys.argv[1:]))

    >
    > If you don't need the flexibility of having the number of elements in
    > your permutation as a parameter - as it seems to be the case in your
    > poker example - simply use nested for-loops, 5 in this case.
    > Example for 5 out of 7 (just to keep the output shorter):
    > for i1 in range(7):
    > for i2 in range(i1+1,7):
    > for i3 in range(i2+1,7):
    > for i4 in range(i3+1,7):
    > for i5 in range(i4+1,7):
    > print i1,i2,i3,i4,i5
    >
    > 0 1 2 3 4
    > 0 1 2 3 5
    > 0 1 2 3 6
    > 0 1 2 4 5
    > 0 1 2 4 6
    > 0 1 2 5 6
    > 0 1 3 4 5
    > 0 1 3 4 6
    > 0 1 3 5 6
    > 0 1 4 5 6
    > 0 2 3 4 5
    > 0 2 3 4 6
    > 0 2 3 5 6
    > 0 2 4 5 6
    > 0 3 4 5 6
    > 1 2 3 4 5
    > 1 2 3 4 6
    > 1 2 3 5 6
    > 1 2 4 5 6
    > 1 3 4 5 6
    > 2 3 4 5 6
    >
    > Have fun
    > Michael

    Even faster:
    >>>[(i1,i2,i3,i4,i5) for i1 in range(7) for i2 in range(i1+1,7) for i3

    in range(i2+1,7) for i4 in range(i3+1,7) for i5 in range(i4+1,7)]
    [(0, 1, 2, 3, 4), (0, 1, 2, 3, 5), (0, 1, 2, 3, 6), (0, 1, 2, 4, 5), (0,
    1, 2, 4, 6), (0, 1, 2, 5, 6), (0, 1, 3, 4, 5), (0, 1, 3, 4, 6), (0, 1,
    3, 5, 6), (0, 1, 4, 5, 6), (0, 2, 3, 4, 5), (0, 2, 3, 4, 6), (0, 2, 3,
    5, 6), (0, 2, 4, 5, 6), (0, 3, 4, 5, 6), (1, 2, 3, 4, 5), (1, 2, 3, 4,
    6), (1, 2, 3, 5, 6), (1, 2, 4, 5, 6), (1, 3, 4, 5, 6), (2, 3, 4, 5, 6)]
    Michael
     
    Michael Amrhein, Jan 25, 2006
    #4
  5. Jack Diederich wrote:

    > You might want to look at a specific purpose library for poker hands:
    > http://pokersource.sourceforge.net/


    Nah, evaluating the poker hands is the FUN part! I want to do that myself :)

    > If you really want to do combinations a C extension has already
    > been written (by me).
    >
    > http://probstat.sourceforge.net/
    >
    > import probstat
    > cards = range(52)
    > for (hand) in probstat.Combination(card, 5):
    > pass
    >
    > Takes 1.3 seconds on my laptop instead of 17 seconds for the pure
    > python version which is only one order of magnitude faster.


    This is *exactly* what i wanted! I just installed it and the hand
    generation is down to around 1.2 seconds now, and that I can live with
    :) Now I just have to reduce the running time of the actual hand
    evaluation with an order of magnitude... ;)

    Thanks!

    --
    Frode, SIM

    "Any fool can write code that a computer can understand.
    Good programmers write code that humans can understand"
     
    =?ISO-8859-1?Q?Frode_=D8ijord?=, Jan 25, 2006
    #5
  6. Jack Diederich wrote:

    > You might want to look at a specific purpose library for poker hands:
    > http://pokersource.sourceforge.net/


    Nah, evaluating the poker hands is the FUN part! I want to do that myself :)

    > If you really want to do combinations a C extension has already
    > been written (by me).
    >
    > http://probstat.sourceforge.net/
    >
    > import probstat
    > cards = range(52)
    > for (hand) in probstat.Combination(card, 5):
    > pass
    >
    > Takes 1.3 seconds on my laptop instead of 17 seconds for the pure
    > python version which is only one order of magnitude faster.


    This is *exactly* what i wanted! I just installed it and the hand
    generation is down to around 1.2 seconds now, and that I can live with
    :) Now I just have to reduce the running time of the actual hand
    evaluation with an order of magnitude... ;)

    Thanks!

    --
    Frode, SIM

    "Any fool can write code that a computer can understand.
    Good programmers write code that humans can understand"
     
    =?ISO-8859-1?Q?Frode_=D8ijord?=, Jan 25, 2006
    #6
  7. =?ISO-8859-1?Q?Frode_=D8ijord?=

    Terry Reedy Guest

    "Frode Øijord" <> wrote in message
    news:...
    > However, this is way too slow for my needs. I try to use this to
    > generate all possible 5 card poker hands, but this takes around 17
    > seconds on an Athlon 2200. That's a 2 orders of magnitude too slow for
    > my needs.


    The set of all possible 5-card poker hands is a constant. It appears you
    need it over and over. But it is not clear to me whether you only need a
    generator to iterate over the set or the whole set at once. If the latter,
    one option is to generate it once, save to disk, and read it in. I'd try
    both marshal and cpickle modules for read-in time.

    Terry J. Reedy
     
    Terry Reedy, Jan 25, 2006
    #7
  8. =?ISO-8859-1?Q?Frode_=D8ijord?=

    Paul Rubin Guest

    Frode Øijord <> writes:
    > > cards = range(52)
    > > for (hand) in probstat.Combination(card, 5):
    > > pass
    > > Takes 1.3 seconds on my laptop instead of 17 seconds for the pure
    > > python version which is only one order of magnitude faster.

    >
    > This is *exactly* what i wanted! I just installed it and the hand
    > generation is down to around 1.2 seconds now, and that I can live with :)


    Note that you're looking at 24x more hands than you really need to,
    since poker hand evaluation doesn't change if you re-label the four
    suits. It's not like bridge, where spades beat hearts and so forth.
     
    Paul Rubin, Jan 25, 2006
    #8
  9. =?ISO-8859-1?Q?Frode_=D8ijord?=

    Paul Rubin Guest

    Paul Rubin <http://> writes:
    > Note that you're looking at 24x more hands than you really need to,


    Well, maybe not 24x. The exact number is more complicated. I'm still
    too sleepy to figure this out right now but may think about it later.
     
    Paul Rubin, Jan 25, 2006
    #9
  10. =?ISO-8859-1?Q?Frode_=D8ijord?=

    Paul Rubin Guest

    Paul Rubin <http://> writes:
    > Well, maybe not 24x. The exact number is more complicated. I'm still
    > too sleepy to figure this out right now but may think about it later.


    Turns out to be 7x, for reasons that are a bit mysterious.
    Ignoring suits, think of the 5-card hand as a 5-digit number base 13.
    There are 13**5 such numbers, but 13 of them are impossible as 5-card
    deals (all 5 digits are the same, "5 of a kind"). That leaves
    13**5-13 = 371280, which is 1/7th of C(52,5). Can someone give
    a combinatorial explanation?

    Generating the hands is simple:

    def deals():
    for i in xrange(13**5):
    cards = [(i//p) % 13 for p in (1, 13, 169, 2197, 28561)]
    yield cards

    The funny numbers in that list are the first four powers of 13.
    Flattening the generator with list() takes about 8 sec on my p3-750.
    Unrolling the list comprehension and making tuples instead of lists,
    cards = (i%13, (i//13)%13, (i//169)%13, (i//2197)%13, (i//28561)%13)
    speeds it up to 5.6 seconds.

    In categorizing the hands from this generator, you have to:

    - discard the hands that are 5-of-a-kind (there are 13 of them)

    - in hands where all 5 numbers are distinct, consider whether
    the hand might be a flush (probability is 1 in 256).
     
    Paul Rubin, Jan 25, 2006
    #10
  11. Paul Rubin wrote:

    > def deals():
    > for i in xrange(13**5):
    > cards = [(i//p) % 13 for p in (1, 13, 169, 2197, 28561)]
    > yield cards


    This gives hands like [0,0,0,0,1] and [0,0,0,1,0] which are
    permutations of one another.

    Below is a piece of code that avoids this. Here's how to interprete its
    output. Suppose one gets a hand like [0,1,2,3,4]. This means that it
    would be possible to create 1024 (4**5) poker hands from this, by
    "coloring" the cards.

    Another hand, for example [0,0,1,2,3], would allow only 384 colorings,
    because the two zeros would contribute choose 2 out of 4 (colors), so 6
    colorings. The other numbers remain available for 4 colorings, which
    gives 6*4**3 (==384) colorings for this hand.

    Similar things happen for other partionings of the hands into numbers.
    In fact I am now investigating a description based on integer
    partitions of the number 5. I am not sure whether I want to partition
    based on colors or on numbers, that seems to arbitrary.

    This is very fascinating. Maybe someday I'll make a tkinter script with
    a visual tree structure allowing all kinds of numbers of "cards", and
    arbitrary numbers of variables to partition by.

    This would then give result sets like those strange quantum particles,
    such as quarks.

    Have fun,

    Anton

    def hands(L = [0]):
    if len(L) == 6:
    if L[1] != L[-1]: #no five of a kind
    yield L[1:]
    else:
    for i in range(L[-1],13):
    for H in hands(L+):
    yield H

    def pprint(i,hand):
    print '%5i: ' %i,
    for x in hand:
    print '%2i ' % x,
    print

    def test():
    H = hands()
    total = 0
    for i,x in enumerate(H):
    pprint(i,x)

    if __name__=='__main__':
    test()
     
    Anton Vredegoor, Jan 28, 2006
    #11
  12. =?ISO-8859-1?Q?Frode_=D8ijord?=

    Paul Rubin Guest

    "Anton Vredegoor" <> writes:
    > > def deals():
    > > for i in xrange(13**5):
    > > cards = [(i//p) % 13 for p in (1, 13, 169, 2197, 28561)]
    > > yield cards

    >
    > This gives hands like [0,0,0,0,1] and [0,0,0,1,0] which are
    > permutations of one another.


    Yes, that's intentional, I thought the idea was to figure out the
    probability of each type of poker hand, which means you have to
    count those multiple occurrences.

    > Below is a piece of code that avoids this.


    Nice.

    > Another hand, for example [0,0,1,2,3], would allow only 384 colorings,...
    > Similar things happen for other partionings of the hands into numbers...
    >
    > This is very fascinating. Maybe someday I'll make a tkinter script with
    > a visual tree structure allowing all kinds of numbers of "cards", and
    > arbitrary numbers of variables to partition by.


    Cool, I'd still like to know why (13**5)-13 = C(52,5) other than
    by just doing the arithmetic and comparing the results. Maybe your
    tkinter script can show that.
     
    Paul Rubin, Jan 28, 2006
    #12
  13. Paul Rubin wrote:

    > Cool, I'd still like to know why (13**5)-13 = C(52,5) other than
    > by just doing the arithmetic and comparing the results. Maybe your
    > tkinter script can show that.


    That seems to be very hard :) Unless I'm missing something.

    Anton

    def noverk(n,k):
    return reduce(lambda a,b: a*(n-b)/(b+1),range(k),1)

    print noverk(52,5)
    print 13**5-13

    #prints:

    2598960
    371280
     
    Anton Vredegoor, Jan 29, 2006
    #13
  14. Anton Vredegoor wrote:

    > Paul Rubin wrote:
    >
    > > Cool, I'd still like to know why (13**5)-13 = C(52,5) other than
    > > by just doing the arithmetic and comparing the results. Maybe your
    > > tkinter script can show that.

    >
    > That seems to be very hard :) Unless I'm missing something.


    Like a factor seven, you mentioned that a few posts back. Sorry about
    that.

    Anton
     
    Anton Vredegoor, Jan 29, 2006
    #14
    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. Mathias
    Replies:
    1
    Views:
    1,497
    Robert Kern
    Mar 5, 2005
  2. Mathias
    Replies:
    0
    Views:
    378
    Mathias
    Mar 4, 2005
  3. Christian Meesters
    Replies:
    7
    Views:
    354
    Alan Isaac
    Dec 19, 2006
  4. John W. Long

    HTML Generation (Next Generation CGI)

    John W. Long, Nov 22, 2003, in forum: Ruby
    Replies:
    4
    Views:
    340
    John W. Long
    Nov 24, 2003
  5. Gregory Brown
    Replies:
    1
    Views:
    133
    Gregory Brown
    Sep 13, 2008
Loading...

Share This Page