Re: Combinatorics

On Feb 12, 1:52 am, Michael Robertson <mcrobert...@xxxxxxxxxxx> 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
.

Relevant Pages