Перестановки с уникальными значениями

Ответ 1

class unique_element:
    def __init__(self,value,occurrences):
        self.value = value
        self.occurrences = occurrences

def perm_unique(elements):
    eset=set(elements)
    listunique = [unique_element(i,elements.count(i)) for i in eset]
    u=len(elements)
    return perm_unique_helper(listunique,[0]*u,u-1)

def perm_unique_helper(listunique,result_list,d):
    if d < 0:
        yield tuple(result_list)
    else:
        for i in listunique:
            if i.occurrences > 0:
                result_list[d]=i.value
                i.occurrences-=1
                for g in  perm_unique_helper(listunique,result_list,d-1):
                    yield g
                i.occurrences+=1




a = list(perm_unique([1,1,2]))
print(a)

результат:

[(2, 1, 1), (1, 2, 1), (1, 1, 2)]

РЕДАКТИРОВАТЬ (как это работает):

Я переписал вышеупомянутую программу, чтобы она была длиннее, но более читабельной.

Мне обычно трудно объяснить, как что-то работает, но позвольте мне попробовать. Чтобы понять, как это работает, вы должны понимать похожую, но более простую программу, которая даст все перестановки с повторениями.

def permutations_with_replacement(elements,n):
    return permutations_helper(elements,[0]*n,n-1)#this is generator

def permutations_helper(elements,result_list,d):
    if d<0:
        yield tuple(result_list)
    else:
        for i in elements:
            result_list[d]=i
            all_permutations = permutations_helper(elements,result_list,d-1)#this is generator
            for g in all_permutations:
                yield g

Эта программа, очевидно, намного проще: d обозначает глубину в permutations_helper и имеет две функции. Одна функция является условием остановки нашего рекурсивного алгоритма, а другая - для списка результатов, который передается.

Вместо того, чтобы возвращать каждый результат, мы даем его. Если бы не было функции/оператора yield мы бы поместили результат в некоторую очередь в точке условия остановки. Но таким образом, как только условие остановки выполнено, результат распространяется по всем стекам до вызывающей стороны. Это цель
for g in perm_unique_helper(listunique,result_list,d-1): yield g поэтому каждый результат распространяется до вызывающей стороны.

Вернуться к исходной программе: у нас есть список уникальных элементов. Прежде чем мы сможем использовать каждый элемент, мы должны проверить, сколько из них все еще доступно для добавления в result_list. Работа с этой программой очень похожа на permutations_with_replacement. Разница в том, что каждый элемент не может повторяться больше раз, чем в perm_unique_helper.

Ответ 2

Потому что иногда новые вопросы помечены как дубликаты, и их авторы ссылаются на этот вопрос, может быть важно отметить, что sympy имеет итератор для этой цели.

>>> from sympy.utilities.iterables import multiset_permutations
>>> list(multiset_permutations([1,1,1]))
[[1, 1, 1]]
>>> list(multiset_permutations([1,1,2]))
[[1, 1, 2], [1, 2, 1], [2, 1, 1]]

Ответ 3

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

from itertools import permutations

def unique_permutations(iterable, r=None):
    previous = tuple()
    for p in permutations(sorted(iterable), r):
        if p > previous:
            previous = p
            yield p

for p in unique_permutations('cabcab', 2):
    print p

дает

('a', 'a')
('a', 'b')
('a', 'c')
('b', 'a')
('b', 'b')
('b', 'c')
('c', 'a')
('c', 'b')
('c', 'c')

Ответ 4

Вы можете попробовать использовать set:

>>> list(itertools.permutations(set([1,1,2,2])))
[(1, 2), (2, 1)]

Вызов для удаления удаленных дубликатов

Ответ 5

Грубо так же быстро, как Лука Ране отвечает, но короче и проще, ИМХО.

def unique_permutations(elements):
    if len(elements) == 1:
        yield (elements[0],)
    else:
        unique_elements = set(elements)
        for first_element in unique_elements:
            remaining_elements = list(elements)
            remaining_elements.remove(first_element)
            for sub_permutation in unique_permutations(remaining_elements):
                yield (first_element,) + sub_permutation

>>> list(unique_permutations((1,2,3,1)))
[(1, 1, 2, 3), (1, 1, 3, 2), (1, 2, 1, 3), ... , (3, 1, 2, 1), (3, 2, 1, 1)]

Он работает рекурсивно, устанавливая первый элемент (итерируя через все уникальные элементы) и повторяя через перестановки для всех остальных элементов.

Пройдите через unique_permutations (1,2,3,1), чтобы увидеть, как он работает:

• unique_elements - 1,2,3
• Пусть итерация через них: first_element начинается с 1.
  • remaining_elements - [2,3,1] (т.е. 1,2,3,1 минус первый 1)
  • Мы перебираем (рекурсивно) через перестановки остальных элементов: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)
  • Для каждого sub_permutation мы вставляем first_element: ( 1, 1,2,3), ( 1, 1,3,2),... и дать результат.
• Теперь мы переходим к first_element= 2 и делаем то же самое, что и выше.
  • remaining_elements - [1,3,1] (т.е. 1,2,3,1 минус первые 2)
  • Мы перебираем через перестановки остальных элементов: (1, 1, 3), (1, 3, 1), (3, 1, 1)
  • Для каждого sub_permutation вставляем first_element: ( 2, 1, 1, 3), ( 2, 1, 3, 1), ( 2, 3, 1, 1)... и дать результат.
• Наконец, мы делаем то же самое с first_element= 3.

Ответ 6

Это мое решение с 10 строками:

class Solution(object):
    def permute_unique(self, nums):
        perms = [[]]
        for n in nums:
            new_perm = []
            for perm in perms:
                for i in range(len(perm) + 1):
                    new_perm.append(perm[:i] + [n] + perm[i:])
                    # handle duplication
                    if i < len(perm) and perm[i] == n: break
            perms = new_perm
        return perms


if __name__ == '__main__':
    s = Solution()
    print s.permute_unique([1, 1, 1])
    print s.permute_unique([1, 2, 1])
    print s.permute_unique([1, 2, 3])

--- Результат ----

[[1, 1, 1]]
[[1, 2, 1], [2, 1, 1], [1, 1, 2]]
[[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]]

Ответ 7

Наивный подход может заключаться в том, чтобы взять множество перестановок:

list(set(it.permutations([1, 1, 1])))
# [(1, 1, 1)]

Однако этот метод расточительно вычисляет репликативные перестановки и отбрасывает их. Более эффективным подходом было бы more_itertools.distinct_permutations, стороннего инструмента.

Код

import itertools as it

import more_itertools as mit


list(mit.distinct_permutations([1, 1, 1]))
# [(1, 1, 1)]

Спектакль

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

iterable = [1, 1, 1, 1, 1, 1]
len(list(it.permutations(iterable)))
# 720

%timeit -n 10000 list(set(it.permutations(iterable)))
# 10000 loops, best of 3: 111 µs per loop

%timeit -n 10000 list(mit.distinct_permutations(iterable))
# 10000 loops, best of 3: 16.7 µs per loop

Мы видим, что more_itertools.distinct_permutations на порядок выше.

подробности

Из источника алгоритм рекурсии (как показано в принятом ответе) используется для вычисления различных перестановок, тем самым устраняя расточительные вычисления. Подробнее см. Исходный код.

Ответ 8

Звучит так, будто вы ищете itertools.combinations() docs.python.org

list(itertools.combinations([1, 1, 1],3))
[(1, 1, 1)]

Ответ 9

Ввязался в этот вопрос, ища что-то сам!

Вот что я сделал:

def dont_repeat(x=[0,1,1,2]): # Pass a list
    from itertools import permutations as per
    uniq_set = set()
    for byt_grp in per(x, 4):
        if byt_grp not in uniq_set:
            yield byt_grp
            uniq_set.update([byt_grp])
    print uniq_set

for i in dont_repeat(): print i
(0, 1, 1, 2)
(0, 1, 2, 1)
(0, 2, 1, 1)
(1, 0, 1, 2)
(1, 0, 2, 1)
(1, 1, 0, 2)
(1, 1, 2, 0)
(1, 2, 0, 1)
(1, 2, 1, 0)
(2, 0, 1, 1)
(2, 1, 0, 1)
(2, 1, 1, 0)
set([(0, 1, 1, 2), (1, 0, 1, 2), (2, 1, 0, 1), (1, 2, 0, 1), (0, 1, 2, 1), (0, 2, 1, 1), (1, 1, 2, 0), (1, 2, 1, 0), (2, 1, 1, 0), (1, 0, 2, 1), (2, 0, 1, 1), (1, 1, 0, 2)])

В принципе, создайте набор и продолжайте добавлять к нему. Лучше, чем создавать списки и т.д., Которые занимают слишком много памяти. Надеюсь, это поможет следующему человеку, смотрящему:-) Комментируйте набор "обновление" в функции, чтобы увидеть разницу.

Ответ 10

Рекурсивное решение этой проблемы.

def permutation(num_array):
    res=[]
    if len(num_array) <= 1:
        return [num_array]
    for num in set(num_array):
        temp_array = num_array.copy()
        temp_array.remove(num)
        res += [[num] + perm for perm in permutation(temp_array)]
    return res

arr=[1,2,2]
print(permutation(arr))

Ответ 11

Вы можете создать функцию, которая использует collections.Counter для получения уникальных элементов и их количества из заданной последовательности, а также с помощью itertools.combinations для выбора комбинаций индексов для каждого уникального элемента в каждом рекурсивном вызове и отображения индексов обратно в список, когда все индексы выбраны:

from collections import Counter
from itertools import combinations
def unique_permutations(seq):
    def index_permutations(counts, index_pool):
        if not counts:
            yield {}
            return
        (item, count), *rest = counts.items()
        rest = dict(rest)
        for indices in combinations(index_pool, count):
            mapping = dict.fromkeys(indices, item)
            for others in index_permutations(rest, index_pool.difference(indices)):
                yield {**mapping, **others}
    indices = set(range(len(seq)))
    for mapping in index_permutations(Counter(seq), indices):
        yield [mapping[i] for i in indices]

так что [''.join(i) for я in unique_permutations('moon')] возвращает:

['moon', 'mono', 'mnoo', 'omon', 'omno', 'nmoo', 'oomn', 'onmo', 'nomo', 'oonm', 'onom', 'noom']

Ответ 12

Что насчет

np.unique(itertools.permutations([1, 1, 1]))

Проблема заключается в том, что теперь перестановки представляют собой строки массива Numpy, тем самым используя больше памяти, но вы можете циклически перемещать их по-прежнему

perms = np.unique(itertools.permutations([1, 1, 1]))
for p in perms:
    print p

Ответ 13

Пришел к этому на днях, работая над собственной проблемой. Мне нравится подход Луки Ране, но я думал, что использование класса Counter в библиотеке коллекций показалось скромным улучшением. Здесь мой код:

def unique_permutations(elements):
    "Returns a list of lists; each sublist is a unique permutations of elements."
    ctr = collections.Counter(elements)

    # Base case with one element: just return the element
    if len(ctr.keys())==1 and ctr[ctr.keys()[0]] == 1:
        return [[ctr.keys()[0]]]

    perms = []

    # For each counter key, find the unique permutations of the set with
    # one member of that key removed, and append the key to the front of
    # each of those permutations.
    for k in ctr.keys():
        ctr_k = ctr.copy()
        ctr_k[k] -= 1
        if ctr_k[k]==0: 
            ctr_k.pop(k)
        perms_k = [[k] + p for p in unique_permutations(ctr_k)]
        perms.extend(perms_k)

    return perms

Этот код возвращает каждую перестановку в виде списка. Если вы будете кормить его строкой, она даст вам список перестановок, где каждый из них представляет собой список символов. Если вы хотите, чтобы результат был как список строк (например, если вы ужасный человек, и вы хотите злоупотреблять моим кодом, чтобы помочь вам обмануть Scrabble), просто выполните следующие действия:

[''.join(perm) for perm in unique_permutations('abunchofletters')]

Ответ 14

Я придумал очень подходящую реализацию, используя itertools.product в этом случае (это реализация, где вы хотите, чтобы все комбинации

unique_perm_list = [''.join(p) for p in itertools.product(['0', '1'], repeat = X) if ''.join(p).count() == somenumber]

это по существу комбинация (n над k) с n = X и somenumber = k itertools.product() итерации от k = 0 до k = X, последующая фильтрация с помощью count гарантирует, что только перестановки с правильным числом из них список. вы можете легко увидеть, что он работает, когда вы вычисляете n над k и сравниваете его с len (unique_perm_list)

Ответ 15

Лучшее решение этой проблемы, которое я видел, использует Кнут "Алгоритм L" (как отмечено ранее Герратом в комментариях к оригинальному сообщению):
fooobar.com/info/111868/...

Некоторые сроки:

Сортировка [1]*12+[0]*12 (2 704 156 уникальных перестановок):
Алгоритм L → 2,43 с
Решение Люка Ране → 8,56 с
scipy.multiset_permutations() → 16,8 с