[Python-ideas] Extremely weird itertools.permutations

[Steven D'Aprano]

On Fri, Oct 11, 2013 at 11:38:33AM -0700, Neil Girdhar wrote:
> "It is universally agreed that a list of n distinct symbols has n! 
> permutations. However, when the symbols are not distinct, the most common 
> convention, in mathematics and elsewhere, seems to be to count only 
> distinct permutations." — 

I dispute this entire premise. Take a simple (and stereotypical) 
example, picking balls from an urn. 

Say that you have three Red and Two black balls, and randomly select 
without replacement. If you count only unique permutations, you get only 
four possibilities:

py> set(''.join(t) for t in itertools.permutations('RRRBB', 2))
{'BR', 'RB', 'RR', 'BB'}

which implies that drawing RR is no more likely than drawing BB, which 
is incorrect. The right way to model this experiment is not to count 
distinct permutations, but actual permutations:

py> list(''.join(t) for t in itertools.permutations('RRRBB', 2))
['RR', 'RR', 'RB', 'RB', 'RR', 'RR', 'RB', 'RB', 'RR', 'RR', 'RB', 'RB', 
'BR', 'BR', 'BR', 'BB', 'BR', 'BR', 'BR', 'BB']

which makes it clear that there are two ways of drawing BB compared to 
six ways of drawing RR. If that's not obvious enough, consider the case 
where you have two thousand red balls and two black balls -- do you 
really conclude that there are the same number of ways to pick RR as BB?

So I disagree that counting only distinct permutations is the most 
useful or common convention. If you're permuting a collection of 
non-distinct values, you should expect non-distinct permutations.

I'm trying to think of a realistic, physical situation where you would 
only want distinct permutations, and I can't.


> Should we consider fixing itertools.permutations and to output only unique 
> permutations (if possible, although I realize that would break code). 

Absolutely not. Even if you were right that it should return unique 
permutations, and I strongly disagree that you were, the fact that it 
would break code is a deal-breaker.



-- 
Steven