[Python-ideas] Extremely weird itertools.permutations

[Neil Girdhar]

Hi Raymond,

I agree with you on the consistency point with itertools.product.  That's a
great point.

However, permutations(set(population)) is not the correct way to take the
permutations of a multiset.  Please take a look at how permutations are
taken from a multiset from any of the papers I linked or any paper that you
can find on the internet.  The number of permutations of multiset is n! /
 \prod a_i! for a_i are the element counts — just like I was taught in
school.

There is currently no fast way to find these permutations of a multiset and
it is a common operation for solving problems.  What is needed, I think is
a function multiset_permutations that accepts an iterable.

Best,

Neil


On Sat, Oct 12, 2013 at 8:44 PM, Raymond Hettinger <
raymond.hettinger at gmail.com> wrote:

>
> On Oct 12, 2013, at 11:56 AM, Neil Girdhar <mistersheik at gmail.com> wrote:
>
> , I find the current behaviour surprising and would like to see a
> distinct_permutations function.
>
>  How do I start to submit a patch?
>
>
> You can submit your patch at http://bugs.python.org and assign it to me
> (the module designer and maintainer).
>
> That said, the odds of it being accepted are slim.
> There are many ways to write combinatoric functions
> (Knuth has a whole book on the subject) and I don't
> aspire to include multiple variants unless there are
> strong motivating use cases.
>
> In general, if someone wants to eliminate duplicates
> from the population, they can do so easily with:
>
>    permutations(set(population), n)
>
> The current design solves the most common use cases
> and it has some nice properties such as:
>  * permutations is a subsequence of product
>  * no assumptions are made about the comparability
>    or orderability of members of the population
>  * len(list(permutations(range(n), r))) == n! / (n-r)!
>    just like you were taught in school
>  * it is fast
>
> For more exotic needs, I think is appropriate to look
> outside the standard library to more full-featured
> combinatoric libraries (there are several listed at
> pypi.python.org).
>
>
> Raymond
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20131012/a581ff10/attachment-0001.html>