permutacje o unikalnych wartościach

Polega to na szczegółach implementacji, że każda permutacja posortowanej iterowalnej jest uporządkowana, chyba że są duplikatami wcześniejszych permutacji.

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

Daje

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

Ponieważ czasami nowe pytania są oznaczone jako duplikaty, a ich autorzy są odsyłani do tego pytania, warto wspomnieć, że sympy ma do tego celu iterator.

>>> 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]]

Mniej więcej tak szybka jak odpowiedź luki Rahne, ale krótsza i prostsza, IMHO.

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

Działa rekurencyjnie, ustawiając pierwszy element (iterację przez wszystkie unikalne elementy) i iterację przez permutacje dla wszystkich pozostałych elementów.

Przejrzyjmy unique_permutations z (1,2,3,1), aby zobaczyć, jak to działa:

• unique_elements są 1,2,3
• przejdźmy przez nie: first_element zaczyna się od 1.
  • remaining_elements są [2,3,1] (tj. 1,2,3,1 minus pierwszy 1)
  • iterujemy (rekurencyjnie) przez permutacje pozostałych elementów: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)
  • dla każdego sub_permutation wstawiamy first_element: (1,1,2,3), (1,1,3,2), ... i dać wynik.
• teraz iterujemy do first_element = 2 i robimy to samo, co powyżej.
  • remaining_elements są [1,3,1] (tj. 1,2,3,1 minus pierwsze 2)
  • iterujemy przez permutacje pozostałych elementów: (1, 1, 3), (1, 3, 1), (3, 1, 1)
  • dla każdego sub_permutation wstawiamy first_element: (2, 1, 1, 3), (2, 1, 3, 1), (2, 3, 1, 1)... i dać wynik.
• wreszcie, robimy to samo z first_element = 3.

Możesz spróbować użyć set:

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

Wywołanie ustawiania usuniętych duplikatów

To jest moje rozwiązanie z 10 linijkami:

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

--- wynik - - - -

[[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]]

Wygląda na to, że szukasz itertools.kombinacje () docs.python.org

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

Naiwnym podejściem może być przyjęcie zbioru permutacji:

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

Jednak ta technika niefortunnie oblicza replikacji permutacji i odrzuca je. Bardziej efektywnym podejściem byłoby more_itertools.distinct_permutations, a third-party tool .

Kod

import itertools as it

import more_itertools as mit


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

Wydajność

Używając większej iterowalnej, porównamy występy pomiędzy technikami naiwnymi i zewnętrznymi.

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

Widzimy {[3] } jest rzędem wielkości szybciej.

Szczegóły

Ze źródła, algorytm rekurencyjny (jak widać w zaakceptowanej odpowiedzi) jest używany do obliczania różnych permutacji, co eliminuje marnotrawstwo obliczeń. Więcej informacji można znaleźć w kodzie źródłowym .

Wpadłem na to pytanie, szukając czegoś sam !

Oto co zrobiłem:

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

Zasadniczo, stwórz zestaw i dodawaj do niego. Lepsze niż robienie list itp. to wymaga zbyt wiele pamięci.. Mam nadzieję, że pomoże to następnej osobie wyglądającej: -) Skomentuj zestaw "update" w funkcji, aby zobaczyć różnicę.

Oto rekurencyjne rozwiązanie problemu.

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

A co z

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

Problem polega na tym, że permutacje są teraz rzędami tablicy Numpy, dzięki czemu zużywa się więcej pamięci, ale można je przełączać tak jak wcześniej

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

Natknąłem się na to niedawno, pracując nad własnym problemem. Podoba mi się podejście luki Rahne, ale uznałem, że korzystanie z klasy licznika w bibliotece zbiorów wydaje się skromną poprawą. Oto Mój kod:

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

Ten kod zwraca każdą permutację jako listę. Jeśli podasz mu ciąg znaków, otrzymasz listę permutacji, gdzie każdy z nich jest listą znaków. Jeśli chcesz, aby wyjście było listą ciągów znaków (na przykład, jeśli jesteś okropną osobą i chcesz nadużywać mojego kodu, aby pomóc ci oszukiwać w Scrabble), po prostu wykonaj następujące czynności:]}

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

Wymyśliłem bardzo odpowiednią implementację przy użyciu itertools.produkt w tym przypadku (jest to implementacja, w której chcesz wszystkie kombinacje

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

Jest to zasadniczo kombinacja (n nad k) Z n = X i somenumber = k itertools.product() iteruje od k = 0 do K = X kolejne filtrowanie z count zapewnia, że tylko permutacje z odpowiednią liczbą są rzucane na listę. można łatwo zobaczyć, że to działa, gdy obliczyć n nad k i porównać go do len (unique_perm_list)