Combinatorics

[Michael Robertson]

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?

 

[bearophileHUGS]

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

 

[pataphor]

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.

 

[Steven D'Aprano]

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.

 

[Cameron Laird]

Michael Robertson:

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/

 

[Robert Dodier]

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

 

[bearophileHUGS]

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

 

[mensanator]

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

 

[Jaap Spies]

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

 

[Raymond Hettinger]

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

 

[Cameron Laird]

Cameron Laird:

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.

 

[Thorsten Kampe]

* Michael Robertson (Mon, 11 Feb 2008 23:52:31 -0800)

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

Permutations are also with and without repetition...

Thorsten

 

[Paul Hankin]

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)))