Общепризнано, что список из n различных символов имеет n! Перестановки. Однако, когда символы не отличаются друг от друга, наиболее распространенным соглашением в математике и в других местах, по-видимому, является подсчет только отдельных перестановок. Таким образом, перестановки списка [1, 1, 2]
обычно рассматриваются как
[1, 1, 2], [1, 2, 1], [2, 1, 1]
. В самом деле, следующий код на С++ печатает именно те три:
int a[] = {1, 1, 2};
do {
cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;
} while(next_permutation(a,a+3));
С другой стороны, 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)
Как заметил в ответ пользователь Artiom Rudzenka, документация на Python говорит так:
Элементы рассматриваются как уникальные, основанные на их позиции, а не на их значении.
Мой вопрос: почему было принято это дизайнерское решение?
Похоже, что в соответствии с обычным соглашением результаты будут полезны (и, действительно, это именно то, что я хочу)... или есть какое-то приложение поведения Python, которое мне не хватает?
[Или это проблема с реализацией? Алгоритм, как в next_permutation
- например, объясняется на StackOverflow здесь (мной) и показанным здесь как O (1 ) амортизируется - кажется эффективным и реализуемым в Python, но Python делает что-то еще более эффективно, поскольку он не гарантирует лексикографический порядок, основанный на значении? И если да, то было ли повышение эффективности считалось достойным?]