Combinatorics

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

1. Michael RobertsonGuest

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

2. 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

3. pataphorGuest

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
4. Steven D'ApranoGuest

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
5. Cameron LairdGuest

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
6. Robert DodierGuest

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
7. 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
8. 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
9. Jaap SpiesGuest

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
10. Raymond HettingerGuest

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
11. Cameron LairdGuest

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
12. Thorsten KampeGuest

Thorsten Kampe, Feb 13, 2008
13. Paul HankinGuest

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