具有唯一值的排列

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

因为有时新问题被标记为重复项，并且它们的作者被引用到这个问题，所以可能需要提及 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 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): 产量 g
因此每个结果都会传播给调用者。

回到原来的程序：
我们有一个独特元素的列表。在我们可以使用每个元素之前，我们必须检查其中有多少元素仍然可以推送到 result_list 上。使用此程序与permutations_with_replacement非常相似。不同之处在于每个元素的重复次数不能超过 perm_unique_helper 中的重复次数。

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

它通过设置第一个元素（迭代所有唯一元素）并迭代所有剩余元素的排列来递归地工作。

让我们浏览一下 (1,2,3,1) 的 unique_permutations 来看看它是如何工作的：

• 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 strong>, 1, 3, 1), (2, 3, 1, 1)...并得出结果。

  
  

• 最后，我们对 first_element = 3 执行相同的操作。

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

---

详细信息

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

Answer 6

您可以尝试使用 set：

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

对 set 的调用删除了重复项

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

Answer 8

我见过的这个问题的最佳解决方案是使用 Knuth 的“算法 L”（正如 Gerrat 之前在原始帖子的评论中指出的那样）：
<一href="http://stackoverflow.com/questions/12836385/how-can-i-interleave-or-create-unique-permutations-of-two-stings-without-recurs/12837695 ">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 s
Luke Rahne 的解 → 8.56 s
scipy.multiset_permutations() → 16.8 秒

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

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

注意，不会创建重复项（例如与 < 组合的项目） code>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()

Answer 11

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

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

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

基本上，制作一组并不断添加。比制作​​占用太多内存的列表等更好。
希望它对下一个人有所帮助:-) 注释掉函数中设置的“更新”以查看差异。

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

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

Answer 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 -排列/

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

Answer 17

在这种情况下，我使用 itertools.product 提出了一个非常合适的实现（这是一个您想要所有组合的实现，

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

这本质上是一个组合（n over k），其中 n = X 和 somenumber = k
itertools.product() 从 k = 0 迭代到 k = X，随后使用 count 进行过滤，确保只有具有正确数量的排列才会被投射到列表中。当您计算 n over k 并将其与 len(unique_perm_list) 进行比较时，您可以轻松地看到它的工作原理

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

Answer 19

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

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

Answer 20

问题

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

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

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