Почему Python itertools.permutations содержит дубликаты?(Когда в оригинальном списке есть дубликаты)

Question

Общепризнано, что список из n различных символов имеет n!Перестановки.Тем не менее, когда символы не различаются, наиболее распространенным соглашением в математике и других областях, по-видимому, является подсчет только различных перестановок.Таким образом, перестановки списка [1, 1, 2] обычно считаются
[1, 1, 2], [1, 2, 1], [2, 1, 1].Действительно, следующий код C ++ печатает именно эти три:

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)

Как указал пользователь Artsiom Rudzenka в ответе, документация Python гласит:

Элементы обрабатываются как уникальные в зависимости от их положения, а не от их стоимости..

Мой вопрос: почему было принято это дизайнерское решение?

Кажется, что следование обычному соглашению дало бы результаты, которые были бы более полезными (и действительно, обычно это именно то, что я хочу) ... или есть какое-то применение поведения Python, которое я пропускаю?

[Или это какая-то проблема с реализацией?Алгоритм, как в next_permutation - например, объясненный для StackOverflow здесь (мной) и , показанный здесь как амортизированный O (1) - кажется эффективным и реализуемым в Python, ноPython делает что-то еще более эффективное, поскольку он не гарантирует лексикографический порядок, основанный на значении?И если да, то стоило ли считать повышение эффективности?]

Answer 1

Я не могу говорить за дизайнера itertools.permutations (Раймонд Хеттингер), но мне кажется, что есть несколько моментов в пользу дизайна:

Во-первых, если вы использовалиnext_permutation в стиле, тогда вы будете ограничены в передаче объектов, которые поддерживают линейное упорядочение.Принимая во внимание, что 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, а не вместо нее.Почему бы не написать такую ​​функцию и не отправить патч?

Answer 2

Я принимаю ответ Гарета Риса как наиболее привлекательное объяснение (если не считать ответа от разработчиков библиотеки Python), а именно, что itertools.permutations в Python не сравнивает значения элементов. Если подумать, это вопрос, о котором спрашивается, но теперь я вижу, как это можно рассматривать как преимущество, в зависимости от того, для чего обычно используется itertools.permutations.

Просто для полноты я сравнил три метода генерации всех различных перестановок. Метод 1, который очень неэффективен в отношении памяти и времени, но требует наименьшего количества нового кода, состоит в том, чтобы обернуть itertools.permutations Python, как в ответе Zeekay. Метод 2 - это основанная на генераторе версия C ++ next_permutation, из этого сообщения в блоге . Метод 3 - это то, что я написал, это даже ближе к алгоритму C ++ 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

Код здесь , если кто-то хочет исследовать.

Answer 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.permutations к itertools, чтобы генерировать перестановки без дубликатов более эффективно.

Answer 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)

Answer 5

Может быть, я ошибаюсь, но кажется, что причина этого в 'Элементы рассматриваются как уникальные в зависимости от их положения, а не от их стоимости. Поэтому, если входные элементы уникальны, повторных значений в каждой перестановке не будет. ' Вы указали (1,1,2) и с вашей точки зрения 1 в индексе 0 и 1 в индексе 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)]), поскольку значения являются уникальными.