고유 한 값이있는 순열

고유 한 값이있는 순열

---

itertools.permutations는 요소가 값이 아닌 위치에 따라 고유하게 취급되는 위치를 생성합니다. 그래서 기본적으로 다음과 같은 중복을 피하고 싶습니다.

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

제 경우에는 순열의 양이 너무 커서 나중에 필터링이 불가능합니다.

누구든지 이것에 적합한 알고리즘을 알고 있습니까?

대단히 감사합니다!

편집하다:

기본적으로 원하는 것은 다음과 같습니다.

x = itertools.product((0, 1, 'x'), repeat=X)
x = sorted(x, key=functools.partial(count_elements, elem='x'))

sorted목록을 만들고 itertools.product의 출력이 너무 크기 때문에 불가능합니다 .

죄송합니다. 실제 문제를 설명 했어야합니다.

---

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에서보다 더 많이 반복 될 수 없다는 것입니다.

---

때때로 새로운 질문이 중복으로 표시되고 그 작성자가이 질문에 언급 되기 때문에 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]]

---

이는 정렬 된 반복 가능 항목의 순열이 이전 순열과 중복되지 않는 한 정렬 된 순서라는 구현 세부 사항에 의존합니다.

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

---

set을 사용해 볼 수 있습니다.

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

제거 된 중복을 설정하는 호출

---

대략 Luka Rahne의 대답만큼 빠르지 만 더 짧고 간단합니다.

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으로 똑같이 합니다.

---

이것은 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]]

---

순진한 접근 방식은 일련의 순열을 취하는 것입니다.

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을 사용하여 순진한 기술과 타사 기술 간의 성능을 비교합니다.

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는 훨씬 더 빠릅니다.

---

세부

소스에서 재귀 알고리즘 (허용 된 답변에서 볼 수 있음)을 사용하여 고유 한 순열을 계산하여 낭비적인 계산을 제거합니다. 자세한 내용은 소스 코드 를 참조하십시오.

---

itertools.combinations () docs.python.org를 찾는 것처럼 들립니다.

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

---

직접 무언가를 찾는 동안이 질문에 부딪 혔습니다!

내가 한 일은 다음과 같습니다.

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

기본적으로 세트를 만들고 계속 추가하십시오. 너무 많은 메모리를 차지하는 목록 등을 만드는 것보다 낫습니다. 다음 사람이 알아볼 수 있기를 바랍니다. :-) 함수에서 '업데이트'세트를 주석 처리하여 차이점을 확인하십시오.

---

다음은 문제에 대한 재귀 적 해결책입니다.

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

---

You can make a function that uses collections.Counter to get unique items and their counts from the given sequence, and uses itertools.combinations to pick combinations of indices for each unique item in each recursive call, and map the indices back to a list when all indices are picked:

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]

so that [''.join(i) for i in unique_permutations('moon')] returns:

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

---

What about

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

The problem is the permutations are now rows of a Numpy array, thus using more memory, but you can cycle through them as before

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

---

Came across this the other day while working on a problem of my own. I like Luka Rahne's approach, but I thought that using the Counter class in the collections library seemed like a modest improvement. Here's my code:

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

This code returns each permutation as a list. If you feed it a string, it'll give you a list of permutations where each one is a list of characters. If you want the output as a list of strings instead (for example, if you're a terrible person and you want to abuse my code to help you cheat in Scrabble), just do the following:

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

---

I came up with a very suitable implementation using itertools.product in this case (this is an implementation where you want all combinations

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

this is essentially a combination (n over k) with n = X and somenumber = k itertools.product() iterates from k = 0 to k = X subsequent filtering with count ensures that just the permutations with the right number of ones are cast into a list. you can easily see that it works when you calculate n over k and compare it to the len(unique_perm_list)

---

The best solution to this problem I have seen uses Knuth's "Algorithm L" (as noted previously by Gerrat in the comments to the original post):
http://stackoverflow.com/questions/12836385/how-can-i-interleave-or-create-unique-permutations-of-two-stings-without-recurs/12837695

Some timings:

Sorting [1]*12+[0]*12 (2,704,156 unique permutations):
Algorithm L → 2.43 s
Luke Rahne's solution → 8.56 s
scipy.multiset_permutations() → 16.8 s

참고URL : https://stackoverflow.com/questions/6284396/permutations-with-unique-values