Combinatorics

Discussion in 'Python' started by Michael Robertson, Feb 12, 2008.

  1. Where is the python equivalent of:

    http://search.cpan.org/~fxn/Algorithm-Combinatorics-0.16/Combinatorics.pm

    combinations (with and without repetition)
    variations (with and without repetition)
    permutations
    partitions
    derangements
    etc

    I'm guessing sage has this, but shouldn't something like this be part of
    the standard library (perhaps in C)? I'd understand if derangements and
    partitions were excluded, but the standard combinatorics (replacement
    on/off, repetition on/off) would be quite nice. It would also be
    helpful to have a general cartesian product function which combined
    elements from an arbitrary number of lists.

    It seems that questions for these algorithms occur too frequently.

    Am I wishing on a star?
     
    Michael Robertson, Feb 12, 2008
    #1
    1. Advertising

  2. Michael Robertson

    Guest

    Michael Robertson:
    > I'm guessing sage has this, but shouldn't something like this be part of
    > the standard library (perhaps in C)?


    My answer is positive. As a reference point you can look at the
    combinatorics module of Mathematica.

    Bye,
    bearophile
     
    , Feb 12, 2008
    #2
    1. Advertising

  3. Michael Robertson

    pataphor Guest

    On Mon, 11 Feb 2008 23:52:31 -0800
    Michael Robertson <> wrote:

    > Am I wishing on a star?


    for i in xrange(10**10):
    print i
    OverflowError: long int too large to convert to int

    The problem seems to be that although python supports arbitrary long
    integers, all the internal loop counters still use limited size integers.

    I'm not arguing that any program would conceivably finish the above
    loop in a reasonable time, but I think it should be possible to use
    itertools.islice to get a smaller slice of this iterator (somewhere in
    the middle) and iterate on that. Maybe it could be done with something
    like "from __future__ import use_long_integers".

    P.
     
    pataphor, Feb 12, 2008
    #3
  4. On Tue, 12 Feb 2008 10:38:53 +0100, pataphor wrote:

    > On Mon, 11 Feb 2008 23:52:31 -0800
    > Michael Robertson <> wrote:
    >
    >> Am I wishing on a star?

    >
    > for i in xrange(10**10):
    > print i
    > OverflowError: long int too large to convert to int
    >
    > The problem seems to be that although python supports arbitrary long
    > integers, all the internal loop counters still use limited size
    > integers.


    I'm curious what you think this has to do with the Original Poster's
    question, which was about combinatorics (as the subject says),
    specifically asking where he could find a library to deal with them.


    --
    Steven
     
    Steven D'Aprano, Feb 12, 2008
    #4
  5. In article <>,
    <> wrote:
    >Michael Robertson:
    >> I'm guessing sage has this, but shouldn't something like this be part of
    >> the standard library (perhaps in C)?

    >
    >My answer is positive. As a reference point you can look at the
    >combinatorics module of Mathematica.

    .
    .
    .
    Should combinatorics be part of the standard library? That's
    an aesthetic-pragmatic question I don't feel competent to
    answer; I look to timbot and Guido and so on for judgment there.
    It does occur to me, though, that even more widely applicable
    than the combinatorics module of Mathematica (if only because of
    its licensing) might be such resources as
    A. http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/190465
    B. http://www.sagemath.org/doc/html/ref/node181.html
    C. http://web.archive.org/web/20070306153113/http://www.unixreview.com/documents/s=10089/ur0606j/
     
    Cameron Laird, Feb 12, 2008
    #5
  6. Cameron Laird wrote:

    > Should combinatorics be part of the standard library? That's
    > an aesthetic-pragmatic question I don't feel competent to
    > answer; I look to timbot and Guido and so on for judgment there.
    > It does occur to me, though, that even more widely applicable
    > than the combinatorics module of Mathematica (if only because of
    > its licensing) might be such resources as

    [...]

    Well, since Mathematica has been mentioned, I'll go ahead and
    mention Maxima as well. Maxima is an open source (GPL) symbolic
    computation system, which includes some functions for
    combinatorics, among many other things. The relevant code is:
    http://maxima.cvs.sourceforge.net/maxima/maxima/src/nset.lisp
    (Oh, btw Maxima is written in Lisp.) The relevant documentation:
    http://maxima.sourceforge.net/docs/manual/en/maxima_37.html

    Sage can presumably access Maxima's combinatoric functions
    (since Sage bundles Maxima along with other programs).
    I don't know if there are combinatoric functions from other
    packages in Sage.

    FWIW

    Robert Dodier
     
    Robert Dodier, Feb 12, 2008
    #6
  7. Michael Robertson

    Guest

    Cameron Laird:
    > It does occur to me, though, that even more widely applicable
    > than the combinatorics module of Mathematica (if only because of
    > its licensing) might be such resources as


    What I was trying to say is that that Mathematica combinatorics module
    contains lots and lots and lots of things, so people that want to
    create a combinatorics module for the Python std lib may read that
    huge list of good ideas as a starting point.

    Bye,
    bearophile
     
    , Feb 12, 2008
    #7
  8. Michael Robertson

    Guest

    On Feb 12, 1:52 am, Michael Robertson <> wrote:
    > Where is the python equivalent of:
    >
    > http://search.cpan.org/~fxn/Algorithm-Combinatorics-0.16/Combinatoric...
    >
    > combinations (with and without repetition)
    > variations (with and without repetition)
    > permutations
    > partitions
    > derangements
    > etc
    >
    > I'm guessing sage has this, but shouldn't something like this be part of
    > the standard library (perhaps in C)?  I'd understand if derangements and
    > partitions were excluded, but the standard combinatorics (replacement
    > on/off, repetition on/off) would be quite nice.  It would also be
    > helpful to have a general cartesian product function which combined
    > elements from an arbitrary number of lists.
    >
    > It seems that questions for these algorithms occur too frequently.
    >
    > Am I wishing on a star?


    Did you know that you can do a Cartesian Product
    (permutations with replacement) using SQL?

    And that things like Combinations with Replacement,
    Permutaions withour Replacement and Combinations
    without Replacement are simple Cartesian Product
    subsets which can be seleceted via a WHERE clause?

    For example:

    # unjoined tables create a Cartesian Product

    import sqlite3

    con = sqlite3.connect(":memory:")
    cur = con.cursor()
    cur.executescript("""
    create table letter(n);
    """)

    letters = [('a'),('b'),('c'),('d'),('e'),('f'),('g'),('h')]

    cur.executemany("""
    INSERT INTO letter(n)
    VALUES (?);"""
    , letters)

    # note: no JOIN clause
    cur.execute("""
    SELECT letter.*,
    letter1.*
    FROM letter, letter AS letter1
    ORDER BY letter.n;
    """)

    cartesian_product = cur.fetchall()

    for i in cartesian_product:
    print i[0]+i[1],

    ## aa ab ac ad ae af ag ah
    ## ba bb bc bd be bf bg bh
    ## ca cb cc cd ce cf cg ch
    ## da db dc dd de df dg dh
    ## ea eb ec ed ee ef eg eh
    ## fa fb fc fd fe ff fg fh
    ## ga gb gc gd ge gf gg gh
    ## ha hb hc hd he hf hg hh
     
    , Feb 12, 2008
    #8
  9. Michael Robertson

    Jaap Spies Guest

    Robert Dodier wrote:
    > Cameron Laird wrote:
    >
    >> Should combinatorics be part of the standard library? That's
    >> an aesthetic-pragmatic question I don't feel competent to
    >> answer; I look to timbot and Guido and so on for judgment there.
    >> It does occur to me, though, that even more widely applicable
    >> than the combinatorics module of Mathematica (if only because of
    >> its licensing) might be such resources as

    > [...]
    >
    > Well, since Mathematica has been mentioned, I'll go ahead and
    > mention Maxima as well. Maxima is an open source (GPL) symbolic
    > computation system, which includes some functions for
    > combinatorics, among many other things. The relevant code is:
    > http://maxima.cvs.sourceforge.net/maxima/maxima/src/nset.lisp
    > (Oh, btw Maxima is written in Lisp.) The relevant documentation:
    > http://maxima.sourceforge.net/docs/manual/en/maxima_37.html
    >
    > Sage can presumably access Maxima's combinatoric functions
    > (since Sage bundles Maxima along with other programs).
    > I don't know if there are combinatoric functions from other
    > packages in Sage.


    There is a native combinatorics module in Sage. See:
    http://www.sagemath.org/doc/html/ref/node181.html

    Sage: http://www.sagemath.org/


    Jaap




    >
    > FWIW
    >
    > Robert Dodier
     
    Jaap Spies, Feb 12, 2008
    #9
  10. On Feb 11, 11:52 pm, Michael Robertson <>
    wrote:
    > Where is the python equivalent of:
    >
    > http://search.cpan.org/~fxn/Algorithm-Combinatorics-0.16/Combinatoric...
    >
    > combinations (with and without repetition)
    > variations (with and without repetition)
    > permutations
    > partitions
    > derangements
    > etc
    >
    > I'm guessing sage has this, but shouldn't something like this be part of
    > the standard library (perhaps in C)?  I'd understand if derangements and
    > partitions were excluded, but the standard combinatorics (replacement
    > on/off, repetition on/off) would be quite nice.  It would also be
    > helpful to have a general cartesian product function which combined
    > elements from an arbitrary number of lists.
    >
    > It seems that questions for these algorithms occur too frequently.
    >
    > Am I wishing on a star?


    FWIW, I'm adding cartesian product to the itertools module in Py2.6.


    Raymond
     
    Raymond Hettinger, Feb 13, 2008
    #10
  11. In article <>,
    <> wrote:
    >Cameron Laird:
    >> It does occur to me, though, that even more widely applicable
    >> than the combinatorics module of Mathematica (if only because of
    >> its licensing) might be such resources as

    >
    >What I was trying to say is that that Mathematica combinatorics module
    >contains lots and lots and lots of things, so people that want to
    >create a combinatorics module for the Python std lib may read that
    >huge list of good ideas as a starting point.

    .
    .
    .
    Certainly; and I see that I neglected to make explicit that one
    possible response to this thread would be to begin contributing
    (pure-Python) combinatoric recipes to the Cookbook.
     
    Cameron Laird, Feb 13, 2008
    #11
  12. Thorsten Kampe, Feb 13, 2008
    #12
  13. Michael Robertson

    Paul Hankin Guest

    On Feb 12, 7:52 am, Michael Robertson <> wrote:
    > Where is the python equivalent of:
    >
    > http://search.cpan.org/~fxn/Algorithm-Combinatorics-0.16/Combinatoric...
    >
    > combinations (with and without repetition)
    > variations (with and without repetition)
    > permutations
    > partitions
    > derangements
    > etc
    >
    > I'm guessing sage has this, but shouldn't something like this be part of
    > the standard library (perhaps in C)?  I'd understand if derangements and
    > partitions were excluded, but the standard combinatorics (replacement
    > on/off, repetition on/off) would be quite nice.  It would also be
    > helpful to have a general cartesian product function which combined
    > elements from an arbitrary number of lists.
    >
    > It seems that questions for these algorithms occur too frequently.


    Here's a fairly efficient and short cartesian product:

    def cart_lists(lists, upto, result):
    if not upto:
    yield result
    else:
    for _ in cart_lists(lists, upto - 1, result):
    for a in lists[upto - 1]:
    result[upto - 1] = a
    yield result

    def cartesian_product(*args):
    "Generate the cartesian product of the sequences passed in."
    for x in cart_lists(map(list, args), len(args), [None] *
    len(args)):
    yield tuple(x)

    print list(cartesian_product('ab', 'cd', xrange(3)))

    --
    Paul Hankin
     
    Paul Hankin, Feb 13, 2008
    #13
    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. Carnosaur

    combinatorics question

    Carnosaur, Oct 28, 2003, in forum: C Programming
    Replies:
    17
    Views:
    572
    Carnosaur
    Oct 31, 2003
  2. Xah Lee

    [perl-python] combinatorics fun

    Xah Lee, Feb 10, 2005, in forum: Python
    Replies:
    7
    Views:
    406
    bruno modulix
    Feb 11, 2005
  3. Nic

    Python and Combinatorics

    Nic, May 16, 2006, in forum: Python
    Replies:
    4
    Views:
    1,750
    Gerard Flanagan
    May 16, 2006
  4. none

    Python and Combinatorics

    none, Oct 24, 2007, in forum: Python
    Replies:
    4
    Views:
    545
    Gerard Flanagan
    Oct 26, 2007
  5. Phlip
    Replies:
    4
    Views:
    335
    John Yeung
    Dec 2, 2009
Loading...

Share This Page