具有独特价值的排列

Question

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的输出太大.

对不起,我应该已经描述了实际问题.

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

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

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

Answer 4

与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 做同样的事情.

Answer 5

您可以尝试使用set:

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

设置的调用删除了重复项

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

Answer 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速度快了一个数量级。

细节

从源头来看，递归算法（如接受的答案所示）用于计算不同的排列，从而避免了浪费的计算。请参阅源代码以获取更多详细信息。