如何在不生成重复结果但具有固定字符量的情况下生成置换

Question

我试图找出一种方法来生成一个字符串的所有可能的排列，这个字符串有几个重复的字符，但不生成重复的元组。在

现在我正在使用itertools.permutations()。它可以工作，但我需要删除重复，而且我无法使用set()来删除重复。在

我期待什么样的结果？好吧，例如，我想得到DDRR的所有组合，itertools.permutations()的事情是，我将得到{}大约四次，因为{}看到了{}，就像它们是不同的一样，Rs也是一样

使用list(itertools.permutations('DDRR'))我得到：

[('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')]

我想要的理想结果是：

^{pr2}$

Answer 1

如果字符串包含大量重复字符，则可以使用基于组合的算法来生成排列。在

基本上，这是通过选择一个字母并找到该字母的副本可以去的所有地方。有了这些可能性，你就可以找到下一个字母的所有位置，等等。在

代码：

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

这样运行：

^{pr2}$

两个重要注意事项：

• 这不会生成以任何特定方式排序的输出。如果要排序输出，请在k =之前添加permutations.sort()，将_helper(idxset - set(pos), i+1)替换为_helper(sorted(set(idxset) - set(pos)), i+1)，并将{}替换为{}。这会使函数稍微慢一点。在
• 如果重复次数过多且不平衡，则此函数非常有效。例如，任何基于置换的方法都将永远占用输入'A'*100 + 'B'*2（AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABB），而此方法将几乎立即完成5151个唯一置换。在

Answer 2

这是创建具有重复元素的集合排列的标准方法：计算每个元素的出现次数（例如，使用关联数组或字典），循环字典中的元素，每次将元素追加到排列中，并与字典的其余部分一起递归。不过，对于很长的输入数组，它永远不会很快；但是，很可能什么都不会。在

（JavaScript中的代码示例；我不会说Python；翻译应该很容易。）

function permute(set) { var alphabet = {}; for (var s in set) { if (!alphabet[set[s]]) alphabet[set[s]] = 1; else ++alphabet[set[s]]; } // alphabet = {'a':5, 'b':2, 'r':2, 'c':1, 'd':1} perm("", set.length); function perm(part, level) { for (var a in alphabet) { // every letter in alphabet if (alphabet[a]) { // one or more of this letter available alphabet[a]; // decrement letter count if (level > 1) perm(part + a, level - 1); // recurse with rest else document.write(part + a + "<br>"); // deepest recursion level ++alphabet[a]; // restore letter count } } } } permute(['a','b','r','a','c','a','d','a','b','r','a']); // 83,160 unique permutations // instead of 39,916,800 non- // unique ones plus filtering ；

Answer 3

通常每个置换算法都应该生成n!/(n-r)!结果，但是您可以决定实现一个检查重复的算法，这应该很有趣。在

让我们看看这是否有用。在

def __permutate(self, objectToPermute):
    in_list = []

    for i in range(self.__cur, len(objectToPermute)):
        in_list.append(self.__swap(self.__cur, i, objectToPermute))

    ''' At initial call, self.__cur = 0
       and self.__permSize would be the r in the permutation formula '''
    if self.__cur < self.__permSize - 1:
        self.__cur += 1

        for obj in in_list:
            self.__permutate(obj)

        self.__cur -= 1


    if self.__cur == self.__permSize -1:
        for obj in in_list:
            #this does the job
            if self.norepeat and obj in self.__perm_obj:
                continue
            self.__perm_obj.append(obj[:self.__permSize])

你一定注意到了，我从很久以前写过的一个类中提取出来的，这是一个排列算法，我喜欢称之为瓜算法（别介意）。在

这部分代码所做的只是递归地置换一个对象，在类中使用了一个swap函数，但是您可以很容易地将其编码出来。。。现在，为了避免重复，你要做的就是确保属性self.norepeat = True和每个重复的对象都会被跳过。如果你需要全班上课，我很乐意与你分享

我需要一个反馈，以便知道你是否明白我的意思