[Python-ideas] Extremely weird itertools.permutations

[Stephen J. Turnbull]

Neil Girdhar writes:

 > I honestly think that Python should stick to the mathematical
 > definition of permutations rather than some kind of consensus of
 > the tiny minority of people here.

Is there an agreed mathematical definition of permutations of
*sequences*?  Every definition I can find refers to permutations of
*sets*.  I think any categorist would agree that there are a large
number of maps of _Sequence_ to _Set_, in particular the two obviously
useful ones[1]: the one that takes each element of the sequence to a
*different* element of the corresponding set, and the one that takes
equal elements of the sequence to the *same* element of the
corresponding set.  The corresponding set need not be the underlying
set of the sequence, and which one is appropriate presumably depends
on applications.

 > When next_permutation was added to C++, I believe the whole
 > standards committee discussed it and they came up with the thing
 > that makes the most sense.

To the negligible (in several senses of the word) fraction of humanity
that participates in C++ standardization.  Python is not C++ (thanking
all the Roman and Greek gods, and refusing to identify Zeus with
Jupiter, nor Aphrodite with Venus<wink/>).

 > The fact that dict and set use equality is I think the reason that
 > permutations should use equality.

Sequences are not sets, and dict is precisely the wrong example for
you to use, since it makes exactly the point that values that are
identical may be bound to several different keys.  We don't unify keys
in a dict just because the values are identical (or equal).  Similar,
in representing a sequence as a set, we use a set of ordered pairs,
with the first component an unique integer indicating position, and
the second the sequence element.

Since there are several useful mathematical ways to convert sequences
to sets, and in particular one very similar, if not identical, to the
one you like is enshrined in the very convenient constructor set(), I
think it's useful to leave it as it is.

 > It is universally agreed that a list of n distinct symbols has n!
 > permutations.

But that's because there's really no sensible definition of
"underlying set" for such a list except the set containing exactly the
same elements as the list.[2]  But there is no universal agreement
that "permutations of a list" is a sensible phrase.

For example, although the Wikipedia article Permutation refers to
lists of permutations, linked list representations of data, to the
"list of objects" for use in Cauchy's notation, and to the cycle
representation as a list of sequences, it doesn't once refer to
permutation of a list.

They're obvious not averse to discussing lists, but the word use for
the entity being permuted is invariably "set".


Footnotes: 
[1]  And some maps not terribly useful for our purposes, such as one
that maps all sequences to a singleton.

[2]  A categorist would disagree, but that's not interesting.