生成具有重复元素的列表排列-IT科技

摘要：问题描述：在 Python 中，使用模块生成列表的所有排列非常简单itertools。我遇到的情况是，我使用的序列只有两个字符（即'1122'）。我想生成所有唯一的排列。对于字符串'1122'，有 6 种唯一排列（1122、1212、1221等），但itertools.permutations会产生 24 个...

问题描述：

在 Python 中，使用模块生成列表的所有排列非常简单itertools。我遇到的情况是，我使用的序列只有两个字符（即'1122'）。我想生成所有唯一的排列。

对于字符串'1122'，有 6 种唯一排列（1122、1212、1221等），但itertools.permutations会产生 24 个项目。只记录唯一排列很简单，但由于要考虑所有 720 个项目，因此收集它们将花费比必要更长的时间。

是否存在一个函数或模块可以在生成排列时考虑重复元素，这样我就不必自己编写了？

解决方案 1：

这个网页看起来很有希望。

def next_permutation(seq, pred=cmp):
    """Like C++ std::next_permutation() but implemented as
    generator. Yields copies of seq."""
    def reverse(seq, start, end):
        # seq = seq[:start] + reversed(seq[start:end]) + \n        #       seq[end:]
        end -= 1
        if end <= start:
            return
        while True:
            seq[start], seq[end] = seq[end], seq[start]
            if start == end or start+1 == end:
                return
            start += 1
            end -= 1
    if not seq:
        raise StopIteration
    try:
        seq[0]
    except TypeError:
        raise TypeError("seq must allow random access.")
    first = 0
    last = len(seq)
    seq = seq[:]
    # Yield input sequence as the STL version is often
    # used inside do {} while.
    yield seq[:]
    if last == 1:
        raise StopIteration
    while True:
        next = last - 1
        while True:
            # Step 1.
            next1 = next
            next -= 1
            if pred(seq[next], seq[next1]) < 0:
                # Step 2.
                mid = last - 1
                while not (pred(seq[next], seq[mid]) < 0):
                    mid -= 1
                seq[next], seq[mid] = seq[mid], seq[next]
                # Step 3.
                reverse(seq, next1, last)
                # Change to yield references to get rid of
                # (at worst) |seq|! copy operations.
                yield seq[:]
                break
            if next == first:
                raise StopIteration
    raise StopIteration

>>> for p in next_permutation([int(c) for c in "111222"]):
...     print p
... 
[1, 1, 1, 2, 2, 2]
[1, 1, 2, 1, 2, 2]
[1, 1, 2, 2, 1, 2]
[1, 1, 2, 2, 2, 1]
[1, 2, 1, 1, 2, 2]
[1, 2, 1, 2, 1, 2]
[1, 2, 1, 2, 2, 1]
[1, 2, 2, 1, 1, 2]
[1, 2, 2, 1, 2, 1]
[1, 2, 2, 2, 1, 1]
[2, 1, 1, 1, 2, 2]
[2, 1, 1, 2, 1, 2]
[2, 1, 1, 2, 2, 1]
[2, 1, 2, 1, 1, 2]
[2, 1, 2, 1, 2, 1]
[2, 1, 2, 2, 1, 1]
[2, 2, 1, 1, 1, 2]
[2, 2, 1, 1, 2, 1]
[2, 2, 1, 2, 1, 1]
[2, 2, 2, 1, 1, 1]
>>>

2017-08-12

七年后，这里有一个更好的算法（更清晰）：

from itertools import permutations

def unique_perms(series):
    return {"".join(p) for p in permutations(series)}

print(sorted(unique_perms('1122')))

解决方案 2：

此外，Itertools 还具有以下功能：

more-itertools.distinct_permutations(iterable)
产生可迭代对象中元素的连续不同排列。
等同于set(permutations(iterable))，但不会产生并丢弃重复项。对于较大的输入序列，这种方法更加高效。

from more_itertools import distinct_permutations

for p in distinct_permutations('1122'):
    print(''.join(p))

# 2211
# 2121
# 1221
# 2112
# 1212
# 1122

安装：

pip install more-itertools

解决方案 3：

使用集合使解决方案更简单。使用重复字符和非重复字符的字符串作为输入。

from itertools import permutations

def perm(s):
    return set(permutations(s))
    
    l = '1122'
    
    perm(l)
  
    {('1', '1', '2', '2'),
     ('1', '2', '1', '2'),
     ('1', '2', '2', '1'),
     ('2', '1', '1', '2'),
     ('2', '1', '2', '1'),
     ('2', '2', '1', '1')}
    
    
    l2 = '1234'
    
    perm(l2)

    {('1', '2', '3', '4'),
     ('1', '2', '4', '3'),
     ('1', '3', '2', '4'),
     ('1', '3', '4', '2'),
     ('1', '4', '2', '3'),
     ('1', '4', '3', '2'),
     ('2', '1', '3', '4'),
     ('2', '1', '4', '3'),
     ('2', '3', '1', '4'),
     ('2', '3', '4', '1'),
     ('2', '4', '1', '3'),
     ('2', '4', '3', '1'),
     ('3', '1', '2', '4'),
     ('3', '1', '4', '2'),
     ('3', '2', '1', '4'),
     ('3', '2', '4', '1'),
     ('3', '4', '1', '2'),
     ('3', '4', '2', '1'),
     ('4', '1', '2', '3'),
     ('4', '1', '3', '2'),
     ('4', '2', '1', '3'),
     ('4', '2', '3', '1'),
     ('4', '3', '1', '2'),
     ('4', '3', '2', '1')}

解决方案 4：

这也是一道常见的面试题。如果不能使用标准库模块，可以考虑以下实现：

我们定义一个按字典顺序排列的排列。一旦我们这样做了，我们就可以从最小的排列开始，然后以最小的增量增加它，直到达到最大的排列。

def next_permutation_helper(perm):
    if not perm:
        return perm

    n = len(perm)

    """
    Find k such that p[k] < p[k + l] and entries after index k appear in
    decreasing order.
    """
    for i in range(n - 1, -1, -1):
        if not perm[i - 1] >= perm[i]:
            break

    # k refers to the inversion point
    k = i - 1

    # Permutation is already the max it can be
    if k == -1:
        return []

    """
    Find the smallest p[l] such that p[l] > p[k]
    (such an l must exist since p[k] < p[k + 1].
    Swap p[l] and p[k]
    """
    for i in range(n - 1, k, -1):
        if not perm[k] >= perm[i]:
            perm[i], perm[k] = perm[k], perm[i]
            break

    # Reverse the sequence after position k.
    perm[k + 1 :] = reversed(perm[k + 1 :])

    return perm


def multiset_permutation(A):
    """
    We sort array first and `next_permutation()` will ensure we generate
    permutations in lexicographic order
    """
    A = sorted(A)
    result = list()

    while True:
        result.append(A.copy())
        A = next_permutation_helper(A)
        if not A:
            break

    return result

输出：

>>> multiset_permutation([1, 1, 2, 2])
[[1, 1, 2, 2], [1, 2, 1, 2], [1, 2, 2, 1], [2, 1, 1, 2], [2, 1, 2, 1], [2, 2, 1, 1]]

您可以使用以下行上的连接将可变列表的输出转换为字符串：

result.append("".join(map(str, A.copy())))

要得到：

['1122', '1212', '1221', '2112', '2121', '2211']

解决方案 5：

from more_itertools import distinct_permutations

x = [p for p in distinct_permutations(['M','I','S', 'S', 'I'])]

for item in x:
    
  print(item)

输出：

('I', 'S', 'S', 'I', 'M')
('S', 'I', 'S', 'I', 'M')
('S', 'S', 'I', 'I', 'M')
('I', 'S', 'I', 'S', 'M')
('S', 'I', 'I', 'S', 'M')
('I', 'I', 'S', 'S', 'M')
('I', 'S', 'I', 'M', 'S')
('S', 'I', 'I', 'M', 'S')
('I', 'I', 'S', 'M', 'S')
('I', 'I', 'M', 'S', 'S')
('I', 'S', 'S', 'M', 'I')
('S', 'I', 'S', 'M', 'I')
('S', 'S', 'I', 'M', 'I')
('S', 'S', 'M', 'I', 'I')
('I', 'S', 'M', 'S', 'I')
('S', 'I', 'M', 'S', 'I')
('S', 'M', 'I', 'S', 'I')
('S', 'M', 'S', 'I', 'I')
('I', 'M', 'S', 'S', 'I')
('M', 'I', 'S', 'S', 'I')
('M', 'S', 'I', 'S', 'I')
('M', 'S', 'S', 'I', 'I')
('I', 'S', 'M', 'I', 'S')
('S', 'I', 'M', 'I', 'S')
('S', 'M', 'I', 'I', 'S')
('I', 'M', 'S', 'I', 'S')
('M', 'I', 'S', 'I', 'S')
('M', 'S', 'I', 'I', 'S')
('I', 'M', 'I', 'S', 'S')
('M', 'I', 'I', 'S', 'S')

解决方案 6：

一个非常简单的解决方案，可能类似于所使用的解决方案more_itertools，它利用@Brayoni建议的排列字典顺序，可以通过构建可迭代的索引来完成。

假设你有L = '1122'。你可以用类似下面的方法建立一个非常简单的索引：

index = {x: i for i, x in enumerate(sorted(L))}

假设您有一个的排列P。有L多少个元素并不重要P。字典顺序规定，如果您P使用索引映射到，它必须始终增加。映射P如下：

mapped = tuple(index[e] for e in p)  # or tuple(map(index.__getitem__, p))

现在您可以丢弃小于或等于迄今为止看到的最大值的元素：

def perm_with_dupes(it, n=None):
    it = tuple(it)   # permutations will do this anyway
    if n is None:
        n = len(it)
    index = {x: i for i, x in enumerate(it)}
    maximum = (-1,) * (len(it) if n is None else n)
    for perm in permutations(it, n):
        key = tuple(index[e] for e in perm)
        if key <= maximum: continue
        maximum = key
        yield perm

请注意，除了保留最后一个最大项之外，没有额外的内存开销。''如果愿意，您可以使用连接元组。