Generating all combinations
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
> 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
> 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
> the use cases are likely disjoint -- when I go to my calculator for
> 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
> number of them (except for purposes of estimating how long a search
> take). People look to the math module for things they find on their
> calculator and to the itertools module for high-speed looping
> Also, there is a issue of naming the functions. For combinations, you
> you might think to look for ncombs() or somesuch, but
> 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)
> >>> c
> ('m', 'o', 'e')
> >>> c.find(('m', 't', 'e'))
> >>> 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)!)
More information about the Python-list