This question already has answers here:

Generate permutations of list with repeated elements
(3个答案)
我试图找出一种方法来生成一个字符串的所有可能的排列,这个字符串有几个重复的字符,但没有生成重复的元组。
现在我正在使用itertools.permutations()。它可以工作,但我需要删除重复,我不能使用set()来删除重复。
我期待什么样的结果?好吧,例如,我想得到DDRR的所有组合,itertools.permutations()的问题是,如果DDRRitertools看作是不同的,与D相同,我将得到大约四次R的组合。
我得到:
[('D', 'D', 'R', 'R'), ('D', 'D', 'R', 'R'), ('D', 'R', 'D', 'R'), ('D', 'R', 'R', 'D'), ('D', 'R', 'D', 'R'), ('D', 'R', 'R', 'D'), ('D', 'D', 'R', 'R'), ('D', 'D', 'R', 'R'), ('D', 'R', 'D', 'R'), ('D', 'R', 'R', 'D'), ('D', 'R', 'D', 'R'), ('D', 'R', 'R', 'D'), ('R', 'D', 'D', 'R'), ('R', 'D', 'R', 'D'), ('R', 'D', 'D', 'R'), ('R', 'D', 'R', 'D'), ('R', 'R', 'D', 'D'), ('R', 'R', 'D', 'D'), ('R', 'D', 'D', 'R'), ('R', 'D', 'R', 'D'), ('R', 'D', 'D', 'R'), ('R', 'D', 'R', 'D'), ('R', 'R', 'D', 'D'), ('R', 'R', 'D', 'D')]

我想要的理想结果是:
[('D', 'R', 'R', 'D'), ('R', 'D', 'R', 'D'), ('R', 'R', 'D', 'D'), ('D', 'R', 'D', 'R'), ('D', 'D', 'R', 'R'), ('R', 'D', 'D', 'R')]

最佳答案

如果字符串包含大量重复字符,则可以使用基于组合的算法生成排列。
基本上,这是通过选择一个字母并找到该字母副本可以到达的所有位置来实现的有了这些可能性,你就能找到下一封信的所有地方,以此类推。
代码:

from collections import Counter
from itertools import combinations

def perms_without_reps(s):
    partitions = list(Counter(s).items())
    k = len(partitions)
    def _helper(idxset, i):
        if len(idxset) == 0:
            yield ()
            return
        for pos in combinations(idxset, partitions[i][1]):
            for res in _helper(idxset - set(pos), i+1):
                yield (pos,) + res

    n = len(s)
    for poses in _helper(set(range(n)), 0):
        out = [None] * n
        for i, pos in enumerate(poses):
            for idx in pos:
                out[idx] = partitions[i][0]
        yield out

像这样运行:
for p in perms_without_reps('DDRR'):
    print p

两个重要注意事项:
这不会生成以任何特定方式排序的输出如果要排序输出,请在permutations.sort()之前添加k =,将_helper(idxset - set(pos), i+1)替换为_helper(sorted(set(idxset) - set(pos)), i+1),并将_helper(set(range(n)), 0)替换为_helper(list(range(n)), 0)这将使函数稍微慢一些。
如果您有大量不平衡的重复次数,则此函数工作得非常好例如,任何基于置换的方法都将永远占用输入'A'*100 + 'B'*2AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABB),而此方法将几乎立即完成5151个唯一置换。

关于python - 如何生成排列而不产生重复结果但具有固定数量的字符Python,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/38544460/

10-12 07:39
查看更多