具有唯一值的排列

问题描述：

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

抱歉，我应该描述实际问题。

解决方案 1：

因为有时新的问题被标记为重复，并且他们的作者被引用到这个问题，所以有必要提一下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]]

解决方案 2：

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 中的次数。

解决方案 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：

大致与 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执行相同的操作。

解决方案 5：

一种简单的方法可能是采用排列集：

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

细节

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

解决方案 6：

您可以尝试使用设置：

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

设置删除重复项的调用

解决方案 7：

这是我的解决方案，共 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]]

解决方案 8：

我见过的解决这个问题的最佳方法是使用 Knuth 的“算法 L”（正如 Gerrat 在原帖评论中所说）：

http://stackoverflow.com/questions/12836385/how-can-i-interleave-or-create-unique-permutations-of-two-stings-without-recurs/12837695

一些时间安排：

排序[1]*12+[0]*12（2,704,156 种独特排列）：

算法 L → 2.43 秒

Luke Rahne 的解决方案 → 8.56 秒

scipy.multiset_permutations()→ 16.8 秒

解决方案 9：

这是该问题的递归解决方案。

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

解决方案 10：

为了生成唯一的排列，["A","B","C","D"]我使用以下命令：

from itertools import combinations,chain

l = ["A","B","C","D"]
combs = (combinations(l, r) for r in range(1, len(l) + 1))
list_combinations = list(chain.from_iterable(combs))

生成：

[('A',),
 ('B',),
 ('C',),
 ('D',),
 ('A', 'B'),
 ('A', 'C'),
 ('A', 'D'),
 ('B', 'C'),
 ('B', 'D'),
 ('C', 'D'),
 ('A', 'B', 'C'),
 ('A', 'B', 'D'),
 ('A', 'C', 'D'),
 ('B', 'C', 'D'),
 ('A', 'B', 'C', 'D')]

请注意，不会创建重复项（例如，D不会生成与之组合的项目，因为它们已经存在）。

示例：然后可以通过 Pandas 数据框中的数据为 OLS 模型生成高阶或低阶项。

import statsmodels.formula.api as smf
import pandas as pd

# create some data
pd_dataframe = pd.Dataframe(somedata)
response_column = "Y"

# generate combinations of column/variable names
l = [col for col in pd_dataframe.columns if col!=response_column]
combs = (combinations(l, r) for r in range(1, len(l) + 1))
list_combinations = list(chain.from_iterable(combs))

# generate OLS input string
formula_base = '{} ~ '.format(response_column)
list_for_ols = [":".join(list(item)) for item in list_combinations]
string_for_ols = formula_base + ' + '.join(list_for_ols)

创建...

Y ~ A + B + C + D + A:B + A:C + A:D + B:C + B:D + C:D + A:B:C + A:B:D + A:C:D + B:C:D + A:B:C:D'

然后可以将其传输到您的OLS 回归

model = smf.ols(string_for_ols, pd_dataframe).fit()
model.summary()

解决方案 11：

听起来您正在寻找 itertools.combinations() docs.python.org

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

解决方案 12：

我自己在寻找某些东西时遇到了这个问题！

这是我所做的：

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

基本上，创建一个集合并不断添加。这比制作占用太多内存的列表等要好。希望它能帮助下一个关注的人 :-) 注释掉函数中的集合“更新”以查看差异。

解决方案 13：

您可以创建一个函数，用于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 i in unique_permutations('moon')]返回：

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

解决方案 14：

这是我不使用 set / dict 的尝试，作为使用递归的生成器，但使用字符串作为输入。输出也按自然顺序排列：

def perm_helper(head: str, tail: str):
    if len(tail) == 0:
        yield head
    else:
        last_c = None
        for index, c in enumerate(tail):
            if last_c != c:
                last_c = c
                yield from perm_helper(
                    head + c, tail[:index] + tail[index + 1:]
                )


def perm_generator(word):
    yield from perm_helper("", sorted(word))

例子：

from itertools import takewhile
word = "POOL"
list(takewhile(lambda w: w != word, (x for x in perm_generator(word))))
# output
# ['LOOP', 'LOPO', 'LPOO', 'OLOP', 'OLPO', 'OOLP', 'OOPL', 'OPLO', 'OPOL', 'PLOO', 'POLO']

解决方案 15：

ans=[]
def fn(a, size): 
    if (size == 1): 
        if a.copy() not in ans:
            ans.append(a.copy())
            return

    for i in range(size): 
        fn(a,size-1); 
        if size&1: 
            a[0], a[size-1] = a[size-1],a[0] 
        else: 
            a[i], a[size-1] = a[size-1],a[i]

https://www.geeksforgeeks.org/heaps-algorithm-for-generate-permutations/

解决方案 16：

前几天在解决自己的问题时遇到了这个问题。我喜欢 Luka Rahne 的方法，但我认为使用集合库中的 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

此代码将每个排列作为列表返回。如果您输入一个字符串，它将为您提供一个排列列表，其中每个排列都是一个字符列表。如果您希望输出为字符串列表（例如，如果您是一个糟糕的人，并且您想滥用我的代码来帮助您在拼字游戏中作弊），只需执行以下操作：

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

解决方案 17：

在这种情况下，我想到了一个非常合适的实现，即使用 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 进行过滤可确保仅将具有正确数量的 1 的排列转换为列表。您可以轻松看到，当您计算 n 除以 k 并将其与 len(unique_perm_list) 进行比较时，它是有效的

解决方案 18：

适合消除递归，使用字典和 numba 来获得高性能，但不使用 Yield/Generator 样式，因此内存使用不受限制：

import numba

@numba.njit
def perm_unique_fast(elements): #memory usage too high for large permutations
    eset = set(elements)
    dictunique = dict()
    for i in eset: dictunique[i] = elements.count(i)
    result_list = numba.typed.List()
    u = len(elements)
    for _ in range(u): result_list.append(0)
    s = numba.typed.List()
    results = numba.typed.List()
    d = u
    while True:
        if d > 0:
            for i in dictunique:
                if dictunique[i] > 0: s.append((i, d - 1))
        i, d = s.pop()
        if d == -1:
            dictunique[i] += 1
            if len(s) == 0: break
            continue
        result_list[d] = i
        if d == 0: results.append(result_list[:])
        dictunique[i] -= 1
        s.append((i, -1))
    return results

import timeit
l = [2, 2, 3, 3, 4, 4, 5, 5, 6, 6]
%timeit list(perm_unique(l))
#377 ms ± 26 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

ltyp = numba.typed.List()
for x in l: ltyp.append(x)
%timeit perm_unique_fast(ltyp)
#293 ms ± 3.37 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

assert list(sorted(perm_unique(l))) == list(sorted([tuple(x) for x in perm_unique_fast(ltyp)]))

速度提高了约 30%，但由于列表复制和管理，仍然受到一些影响。

或者不使用 numba 但仍然不使用递归并使用生成器来避免内存问题：

def perm_unique_fast_gen(elements):
    eset = set(elements)
    dictunique = dict()
    for i in eset: dictunique[i] = elements.count(i)
    result_list = list() #numba.typed.List()
    u = len(elements)
    for _ in range(u): result_list.append(0)
    s = list()
    d = u
    while True:
        if d > 0:
            for i in dictunique:
                if dictunique[i] > 0: s.append((i, d - 1))
        i, d = s.pop()
        if d == -1:
            dictunique[i] += 1
            if len(s) == 0: break
            continue
        result_list[d] = i
        if d == 0: yield result_list
        dictunique[i] -= 1
        s.append((i, -1))

解决方案 19：

也许我们可以在这里使用集合来获得唯一的排列

import itertools
print('unique perms >> ', set(itertools.permutations(A)))

解决方案 20：

那么

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

问题是排列现在是 Numpy 数组的行，因此会使用更多内存，但您可以像以前一样循环遍历它们

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