Почему Python-itertools.permutations содержит дубликаты? (Когда исходный список имеет дубликаты)
Общепризнано, что список из 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 делает что-то еще более эффективно, поскольку он не гарантирует лексикографический порядок, основанный на значении? И если да, то было ли повышение эффективности считалось достойным?]
Ответы
Ответ 1
Я не могу говорить о дизайнере itertools.permutations (Raymond Hettinger), но мне кажется, что есть несколько моментов в пользу дизайна:
Во-первых, если вы использовали стиль next_permutation -style, тогда вам будет запрещено передавать объекты, поддерживающие линейный порядок. В то время как itertools.permutations обеспечивает перестановки любого типа объекта. Представьте себе, насколько это было бы неприятно:
>>> list(itertools.permutations([1+2j, 1-2j, 2+j, 2-j]))
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: no ordering relation is defined for complex numbers
Во-вторых, не тестируя равенство на объектах, itertools.permutations избегает оплаты стоимости вызова метода __eq__ в обычном случае, когда это не нужно.
В принципе, itertools.permutations решает общий случай надежно и дешево. Разумеется, существует аргумент, согласно которому itertools должен обеспечивать функцию, которая позволяет избежать дублирования перестановок, но такая функция должна быть в дополнение к itertools.permutations, а не вместо нее. Почему бы не написать такую функцию и отправить патч?
Ответ 2
Я принимаю ответ Гарета Риса как наиболее привлекательное объяснение (за исключением ответа от разработчиков библиотеки Python), а именно, что Python itertools.permutations не сравнивает значения элементов. Подумайте об этом, об этом и спрашивает вопрос, но теперь я вижу, как это можно рассматривать как преимущество, в зависимости от того, что обычно использует itertools.permutations для.
Просто для полноты я сравнил три метода генерации всех различных перестановок. Метод 1, который очень неэффективен по памяти и по времени, но требует наименее нового кода, заключается в том, чтобы обернуть Python itertools.permutations, как в ответе zeekay. Метод 2 представляет собой версию С++ next_permutation на основе генератора, начиная с этого сообщения в блоге. Метод 3 - это то, что я написал, что еще ближе к С++ next_permutation алгоритму; он изменяет список на месте (я не сделал его слишком общим).
def next_permutationS(l):
n = len(l)
#Step 1: Find tail
last = n-1 #tail is from `last` to end
while last>0:
if l[last-1] < l[last]: break
last -= 1
#Step 2: Increase the number just before tail
if last>0:
small = l[last-1]
big = n-1
while l[big] <= small: big -= 1
l[last-1], l[big] = l[big], small
#Step 3: Reverse tail
i = last
j = n-1
while i < j:
l[i], l[j] = l[j], l[i]
i += 1
j -= 1
return last>0
Вот некоторые результаты. У меня есть еще большее уважение к встроенной функции Python: это примерно в три-четыре раза быстрее, чем другие методы, когда все элементы (или почти все) различны. Конечно, когда есть много повторяющихся элементов, использование этого - ужасная идея.
Some results ("us" means microseconds):
l m_itertoolsp m_nextperm_b m_nextperm_s
[1, 1, 2] 5.98 us 12.3 us 7.54 us
[1, 2, 3, 4, 5, 6] 0.63 ms 2.69 ms 1.77 ms
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 6.93 s 13.68 s 8.75 s
[1, 2, 3, 4, 6, 6, 6] 3.12 ms 3.34 ms 2.19 ms
[1, 2, 2, 2, 2, 3, 3, 3, 3, 3] 2400 ms 5.87 ms 3.63 ms
[1, 1, 1, 1, 1, 1, 1, 1, 1, 2] 2320000 us 89.9 us 51.5 us
[1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4] 429000 ms 361 ms 228 ms
Код здесь, если кто-то хочет исследовать.
Ответ 3
Довольно легко получить поведение, которое вы предпочитаете, обернув itertools.permutations, что могло повлиять на решение. Как описано в документации, itertools предназначен как сборник строительных блоков/инструментов для использования в создании собственных итераторов.
def unique(iterable):
seen = set()
for x in iterable:
if x in seen:
continue
seen.add(x)
yield x
for a in unique(permutations([1, 1, 2])):
print a
(1, 1, 2)
(1, 2, 1)
(2, 1, 1)
Однако, как указано в комментариях, это может быть не так эффективно, как вам хотелось бы:
>>> %timeit iterate(permutations([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]))
1 loops, best of 3: 4.27 s per loop
>>> %timeit iterate(unique(permutations([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2])))
1 loops, best of 3: 13.2 s per loop
Возможно, при наличии достаточного интереса к itertools можно добавить новую функцию или необязательный аргумент в itertools.permutations, чтобы генерировать перестановки без дубликатов более эффективно.
Ответ 4
Я также удивляюсь, что itertools не имеет функции для более интуитивного понятия уникальных перестановок. Генерирование повторяющихся перестановок только для выбора уникального среди них не может быть и речи о каком-либо серьезном применении.
Я написал свою собственную итеративную генераторную функцию, которая ведет себя аналогично itertools.permutations, но не возвращает дубликаты. Учитываются только перестановки исходного списка, подписи могут быть созданы со стандартной библиотекой itertools.
def unique_permutations(t):
lt = list(t)
lnt = len(lt)
if lnt == 1:
yield lt
st = set(t)
for d in st:
lt.remove(d)
for perm in unique_permutations(lt):
yield [d]+perm
lt.append(d)
Ответ 5
Возможно, я ошибаюсь, но кажется, что причина этого в Элементы рассматриваются как уникальные, основанные на их позиции, а не на их значении. Поэтому, если входные элементы уникальны, в каждой перестановке не будет повторяющихся значений.
Вы указали (1,1,2) и с вашей точки зрения 1 в индексе 0 и 1 в одном индексе одинаковы - но это не так, поскольку в подстановках реализации python использовались индексы вместо значений.
Итак, если мы посмотрим на реализацию перестановок python по умолчанию, мы увидим, что он использует индексы:
def permutations(iterable, r=None):
pool = tuple(iterable)
n = len(pool)
r = n if r is None else r
for indices in product(range(n), repeat=r):
if len(set(indices)) == r:
yield tuple(pool[i] for i in indices)
Например, если вы измените свой ввод на [1,2,3], вы получите правильные перестановки ([(1, 2, 3), (1, 3, 2), (2, 1, 3), ( 2, 3, 1), (3, 1, 2), (3, 2, 1)]), поскольку значения уникальны.
