Generating all combinations

[Raymond Hettinger]

> Nice one!

It only does partitions of a sequence.  I haven't yet looked at a way
to
do partitions of a set.  Any ideas?


> Raymond, as perhaps *the* principle contributor to itertools, do you feel
> that the combinatorics-related tools should be in their own module? Or is
> that dividing the module too fine?

I like having them in itertools because they form part of the
"iterator algebra"
for splitting, filtering, joining, and combining streams of iterators.


> Would you consider moving permutations() and friends into a module
> together with functions for calculating the number of permutations etc?
>
> e.g. permutations(iterable[, r]) --> permutations object
>      nPr(n, r) --> int

Looked at this a while back.  If the nPr style functions go in, they
will
probably be in the math module (or a new module for integer functions
like gcd and whatnot).  The reason for not keeping them together is
that
the use cases are likely disjoint -- when I go to my calculator for
nCr
I don't expect a listing -- when I need to loop over permutations, I
typically only care about the contents of the permutation, not the
total
number of them (except for purposes of estimating how long a search
will
take).  People look to the math module for things they find on their
calculator and to the itertools module for high-speed looping
constructs.

Also, there is a issue of naming the functions.  For combinations, you
you might think to look for ncombs() or somesuch, but
binomial_coefficient()
is what someone else may be searching for.

What would be nice is to turn the itertool combinatorics into
classes with a len() method, an ability to index to the n-th
iteration, or to find at an arbitrary iteration:

>>> c = combinations('monte', 3)
>>> len(c)
10
>>> c[2]
('m', 'o', 'e')
>>> c.find(('m', 't', 'e'))
5
>>> random.choice(c)
('o', 'n', 'e')

If the input iterable contains repeats, the find() method
would find the first match.

These things are interesting and fun, but they also smell
of feeping-creaturism.


Raymond