[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.python

Combinatorics

Michael Robertson

2/12/2008 7:53:00 AM

Where is the python equivalent of:

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

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?
14 Answers

Bearophile

2/12/2008 8:42:00 AM

0

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

2/12/2008 9:39:00 AM

0

On Mon, 11 Feb 2008 23:52:31 -0800
Michael Robertson <mcrobertson@hotmail.com> 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.

Steven D'Aprano

2/12/2008 11:59:00 AM

0

On Tue, 12 Feb 2008 10:38:53 +0100, pataphor wrote:

> On Mon, 11 Feb 2008 23:52:31 -0800
> Michael Robertson <mcrobertson@hotmail.com> 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

claird

2/12/2008 2:49:00 PM

0

In article <6690be63-aad6-4d55-8043-6d2d2af885de@i29g2000prf.googlegroups.com>,
<bearophileHUGS@lycos.com> 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/Rec...
B. http://www.sagemath.org/doc/html/ref/no...
C. http://web.archive.org/web/20070306153113/http://www.unixreview.com/documents/s=1008...

Robert Dodier

2/12/2008 4:09:00 PM

0

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...
(Oh, btw Maxima is written in Lisp.) The relevant documentation:
http://maxima.sourceforge.net/docs/manual/en/maxi...

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

Bearophile

2/12/2008 7:52:00 PM

0

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

2/12/2008 8:13:00 PM

0

On Feb 12, 1:52 am, Michael Robertson <mcrobert...@hotmail.com> wrote:
> Where is the python equivalent of:
>
> http://search.cpan.org/~fxn/Algorithm-Combinatorics-0.16/Co......
>
> 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

2/12/2008 10:39:00 PM

0

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...
> (Oh, btw Maxima is written in Lisp.) The relevant documentation:
> http://maxima.sourceforge.net/docs/manual/en/maxi...
>
> 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.sag...doc/html/ref/no...

Sage: http://www.sag...


Jaap




>
> FWIW
>
> Robert Dodier

Raymond Hettinger

2/13/2008 4:43:00 AM

0

On Feb 11, 11:52 pm, Michael Robertson <mcrobert...@hotmail.com>
wrote:
> Where is the python equivalent of:
>
> http://search.cpan.org/~fxn/Algorithm-Combinatorics-0.16/Co......
>
> 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

claird

2/13/2008 2:21:00 PM

0

In article <54c0cf86-d244-4c91-b9c1-fd97a2a5e011@j20g2000hsi.googlegroups.com>,
<bearophileHUGS@lycos.com> 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.