Generating all combinations

Mensanator mensanator at aol.com
Thu Jun 4 18:47:05 CEST 2009


On Jun 4, 1:27 am, Raymond Hettinger <pyt... at rcn.com> wrote:
> > 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.

After all, everybody knows that for m items taken n at
a time, the counts are

perm  w/repl = m**n
comb  w/repl = (m+n-1)!/(n!(m-1)!)
perm wo/repl = m!/(m-n)!
comb wo/repl = m!/(n!(m-n)!)

>
> Raymond




More information about the Python-list mailing list