Combinatorics

[Paul Hankin]

On Feb 12, 7: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.

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