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