代码之家 › 专栏 › 技术社区 › JoshD

用重复元素生成列表的置换

permutation python

JoshD · 技术社区 · 15 年前

在Python中,使用itertools模块生成列表的所有排列非常简单。我使用的列表只有两个字符(即“1122”)。我要生成所有唯一的排列。

对于字符串“1122”,有6个唯一的置换(1122、1212、1221等),但itertools.permutation将产生24个项。只记录唯一的排列很简单,但由于考虑了所有720个项目,因此收集它们所需的时间要长得多。

是否有一个函数或模块在生成排列时会考虑重复的元素,这样我就不必自己编写了?

2 回复 | 直到 15 年前

hughdbrown 8 年前

This web page 看起来很有前途。

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]) + \
        #       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年8月12日

七年后,这里有一个更好的算法(为了清晰起见):

from itertools import permutations

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

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

LetzerWille 7 年前

使用set使解决方案更简单。具有重复字符的字符串,以及不重复, 用作输入。

import re
from itertools import permutations

def perm(s):
    l = re.split('\B',s)
    return set(list(permutations(l,len(l))))

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

MarredCheese Lionia Vasilev 6 年前

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