Все согласны с тем, что список из n различных символов имеет n! перестановки. Однако, когда символы неотличимы друг от друга, наиболее распространенным соглашением в математике и других областях, кажется, является подсчет только различных перестановок. Таким образом, перестановки списка [1, 1, 2]
обычно считаются [1, 1, 2], [1, 2, 1], [2, 1, 1]
. Действительно, следующий код C ++ печатает именно эти три:
int a[] = {1, 1, 2};
do {
cout<
С другой стороны, Python itertools.permutations
, кажется, печатает что-то еще:
import itertools
for a in itertools.permutations([1, 1, 2]):
print a
Это печатает
(1, 1, 2)
(1, 2, 1)
(1, 1, 2)
(1, 2, 1)
(2, 1, 1)
(2, 1, 1)
Как указал пользователь Арциом Рудзенка в ответ, документация Python говорит так:
Элементы рассматриваются как уникальные на основании их положения, а не их ценности.
Мой вопрос: почему было принято это дизайнерское решение?
Кажется, что следование обычному соглашению даст более полезные результаты (и действительно, обычно это именно то, что я хочу) ... или есть какое-то применение поведения Python, которое мне не хватает?
[Или это проблема реализации? Алгоритм, как в next_permutation
- например, объясненный на StackOverflow здесь (мной) и , показанный здесь как амортизированный O (1) - кажется эффективным и реализуемым в Python, но делает ли Python что-то еще более эффективное, поскольку он не гарантирует лексикографический порядок на основе значения? И если да, то было ли сочтено, что повышение эффективности того стоит?]