Combinatorics

[mensanator at aol.com]

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