我一直在复习算法以供练习，目前我正在研究一个我非常喜欢的排列算法:

void permute(char* set, int begin, int end) {
    int range = end - begin;

    if (range == 1)
        cout << set << endl;
    else {
        for(int i = 0; i < range; ++i) {
            swap(&set[begin], &set[begin+i]);
            permute(set, begin+1, end);
            swap(&set[begin], &set[begin+i]);
        }
    }
}

我实际上想将其应用于虽然会有很多重复字符的情况，因此我需要能够修改它以防止打印重复排列。

我将如何检测我是否生成了拷贝？我知道我可以将它存储在散列或类似的东西中，但这不是最佳解决方案 - 我更喜欢不需要额外存储的解决方案。有人可以给我建议吗？

PS:我不想使用 STL 置换机制，也不想在某处引用另一个“唯一置换算法”。我想了解用于防止重复的机制，以便在可能的情况下将其构建到学习中。

最佳答案

没有通用的方法可以防止任意函数生成重复项。当然，您始终可以过滤掉重复项，但您不希望这样，并且有充分的理由。因此，您需要一种特殊方法来仅生成非重复项。

一种方法是按递增的字典顺序生成排列。然后你可以只比较"new"排列是否与上一个排列相同，然后跳过它。它变得更好:在 http://en.wikipedia.org/wiki/Permutations#Generation_in_lexicographic_order 给出的按递增字典顺序生成排列的算法甚至根本不生成重复项!

但是，这不是您问题的答案，因为它是一种不同的算法(尽管也基于交换)。

那么，让我们仔细看看您的算法。一个关键观察结果是:

• 一旦一个字符被交换到 begin 位置，它将留在那里用于 permute 的所有嵌套调用。

我们将把它与以下关于排列的一般观察相结合:

• 如果您置换字符串 s，但仅在具有相同字符的位置，s 将保持不变。事实上，对于某些字符 c 的出现，所有重复排列都有不同的顺序，其中 c 出现在相同的位置。

好的，所以我们要做的就是确保每个字符的出现顺序始终与开头相同。代码如下，但是...我不会说 C++，所以我会使用 Python，希望不要声称它是伪代码。

我们从您的原始算法开始，用“伪代码”重写:

def permute(s, begin, end):
    if end == begin + 1:
        print(s)
    else:
        for i in range(begin, end):
            s[begin], s[i] = s[i], s[begin]
            permute(s, begin + 1, end)
            s[begin], s[i] = s[i], s[begin]

和一个使调用更容易的辅助函数:

def permutations_w_duplicates(s):
    permute(list(s), 0, len(s)) # use a list, as in Python strings are not mutable

现在我们扩展 permute 函数，记录某个字符被交换到 begin 位置的次数(即已固定)，我们还记住每个字符出现的原始顺序 (char_number)。我们尝试交换到 begin 位置的每个字符都必须是原始顺序中的下一个更高的字符，即一个字符的修复次数定义了下一个可以修复该字符的哪个原始出现 -我称之为 next_fixable。

def permute2(s, next_fixable, char_number, begin, end):
    if end == begin + 1:
        print(s)
    else:
        for i in range(begin, end):
            if next_fixable[s[i]] == char_number[i]: 
                next_fixable[s[i]] += 1
                char_number[begin], char_number[i] = char_number[i], char_number[begin]

                s[begin], s[i] = s[i], s[begin]
                permute2(s, next_fixable, char_number, begin + 1, end)
                s[begin], s[i] = s[i], s[begin]

                char_number[begin], char_number[i] = char_number[i], char_number[begin]
                next_fixable[s[i]] -= 1

同样，我们使用辅助函数:

def permutations_wo_duplicates(s):
    alphabet = set(s)
    next_fixable = dict.fromkeys(alphabet, 0)
    count = dict.fromkeys(alphabet, 0)
    char_number = [0] * len(s)
    for i, c in enumerate(s):
        char_number[i] = count[c]
        count[c] += 1

    permute2(list(s), next_fixable, char_number, 0, len(s))

就是这样!

差不多。如果你愿意，你可以在这里停下来用 C++ 重写，但如果你对一些测试数据感兴趣，请继续阅读。

我使用了稍微不同的代码进行测试，因为我不想打印所有排列。在 Python 中，您可以将 print 替换为 yield，将函数转换为生成器函数，其结果可以用 for 循环迭代，并且仅在需要时才计算排列。这是我使用的真实代码和测试:

def permute2(s, next_fixable, char_number, begin, end):
    if end == begin + 1:
        yield "".join(s) # join the characters to form a string
    else:
        for i in range(begin, end):
            if next_fixable[s[i]] == char_number[i]:
                next_fixable[s[i]] += 1
                char_number[begin], char_number[i] = char_number[i], char_number[begin]
                s[begin], s[i] = s[i], s[begin]
                for p in permute2(s, next_fixable, char_number, begin + 1, end):
                    yield p
                s[begin], s[i] = s[i], s[begin]
                char_number[begin], char_number[i] = char_number[i], char_number[begin]
                next_fixable[s[i]] -= 1

def permutations_wo_duplicates(s):
    alphabet = set(s)
    next_fixable = dict.fromkeys(alphabet, 0)
    count = dict.fromkeys(alphabet, 0)
    char_number = [0] * len(s)
    for i, c in enumerate(s):
        char_number[i] = count[c]
        count[c] += 1

    for p in permute2(list(s), next_fixable, char_number, 0, len(s)):
        yield p


s = "FOOQUUXFOO"
A = list(permutations_w_duplicates(s))
print("%s has %s permutations (counting duplicates)" % (s, len(A)))
print("permutations of these that are unique: %s" % len(set(A)))
B = list(permutations_wo_duplicates(s))
print("%s has %s unique permutations (directly computed)" % (s, len(B)))

print("The first 10 permutations       :", A[:10])
print("The first 10 unique permutations:", B[:10])

结果:

FOOQUUXFOO has 3628800 permutations (counting duplicates)
permutations of these that are unique: 37800
FOOQUUXFOO has 37800 unique permutations (directly computed)
The first 10 permutations       : ['FOOQUUXFOO', 'FOOQUUXFOO', 'FOOQUUXOFO', 'FOOQUUXOOF', 'FOOQUUXOOF', 'FOOQUUXOFO', 'FOOQUUFXOO', 'FOOQUUFXOO', 'FOOQUUFOXO', 'FOOQUUFOOX']
The first 10 unique permutations: ['FOOQUUXFOO', 'FOOQUUXOFO', 'FOOQUUXOOF', 'FOOQUUFXOO', 'FOOQUUFOXO', 'FOOQUUFOOX', 'FOOQUUOFXO', 'FOOQUUOFOX', 'FOOQUUOXFO', 'FOOQUUOXOF']

请注意，排列的计算顺序与原始算法相同，只是没有重复项。注意是37800*2! * 2! * 4! = 3628800，正如您所期望的那样。

关于c++ - 修改排列算法以防止重复打印输出的策略，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9493098/