Generating all combinations
Raymond Hettinger
python at rcn.com
Thu Jun 4 02:27:50 EDT 2009
> 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
More information about the Python-list
mailing list