[Python-ideas] Extremely weird itertools.permutations

[Neil Girdhar]

Excellent!

My top two names are
1. multiset_permutations (reflects the mathematical name)
2. anagrams

Note that we may also want to add multiset_combinations.  It hasn't been
part of this discussion, but it may be part of another discussion and I
wanted to point this out as I know many of you are future-conscious.

We seem to be all agreed that we want to accept "r", the length of the
permutation desired.

With permutations, the *set* is passed in as a iterable representing
distinct elements.  With multiset_permutations, there are three ways to
pass in the *multiset*:
- 1. an iterable whose elements (or an optional key function applied to
which) are compared using __eq__
- 2. a dict (of which collections.Counter) is a subclass
- 3. an iterable whose elements are key-value pairs and whose values are
counts

Example uses:
1. multiset_permutations(word)
2. multiset_permutations(Counter(word))
3. multiset_permutations(Counter(word).items())

>From a dictionary:
1. multiset_permutations(itertools.chain.from_iterable(itertools.repeat(k,
v) for k, v in d.items()))
2. multiset_permutations(d)
3. multiset_permutations(d.items())

>From an iterable of key-value pairs:
1. multiset_permutations(itertools.chain.from_iterable(itertools.repeat(k,
v) for k, v in it))
2. multiset_permutations({k: v for k, v in it})
3. multiset_permutations(it)

The advantage of 2 is that no elements are compared by
multiset_permutations (so it is simpler and faster).
The advantage of 3 is that no elements are compared, and they need not be
comparable or hashable.  This version is truly a generalization of the
"permutations" function.  This way, for any input "it" you could pass to
permutations, you could equivalently pass zip(it, itertools.repeat(1)) to
multiset_permutations.

Comments?

Neil


On Mon, Oct 14, 2013 at 1:56 PM, Raymond Hettinger <
raymond.hettinger at gmail.com> wrote:

>
> On Oct 13, 2013, at 1:56 PM, Neil Girdhar <mistersheik at gmail.com> wrote:
>
>  I'm now convinced that itertools.permutations is fine as it is.  I am not
> totally convinced that multiset_permutations doesn't belong in itertools,
>
>
> Now that we have a good algorithm,  I'm open to adding this to itertools,
> but it would need to have a name that didn't create any confusion
> with respect to the existing tools, perhaps something like:
>
>     anagrams(population, r)
>
>     Return an iterator over a all distinct r-length permutations
>     of the population.
>
>     Unlike permutations(), element uniqueness is determined
>     by value rather than by position.  Also, anagrams() makes
>     no guarantees about the order the tuples are generated.
>
>
>
> Raymond
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20131014/99750761/attachment.html>