13

我在做一些热心的编程时遇到了这个问题。问题可以表述如下：

对于多集 A，令 P(A) 表示 A 的所有可能排列的集合。P(A) 自然地划分为等价类的不相交子集，等价关系“可以通过循环移位相关联”。通过从每个等价类中生成一个成员来枚举所有这些等价类。

例如，考虑多重集 {0, 1, 1, 2}。排列“0112”和“1201”是唯一排列，但后者可以通过循环移动前者找到，反之亦然。所需的算法不应同时生成两者。

当然，蛮力方法是可能的：只需生成排列——不管循环重复如何——使用任何多集排列算法，并丢弃通过与先前结果比较发现的重复。然而，这在实践中往往效率低下。所需的算法应该需要最少的（如果不是零的话）簿记。

对此问题的任何见解都深表感谢。

4

5 回答 5

8

泽田算法

于 2010-08-12T13:31:42.813 回答
1

自下而上稍微容易一些：

如果 A 只包含 1 个元素，则 P(A) 也包含一个排列。如果 A 仅包含 2 个元素，则很容易看到相同的作品。

现在，假设您已经拥有包含 n 个元素的 A 的所有 P(A)，并且您添加了一个元素。它可以进入 P(A) 中任何排列中的任何 n 个点。

我认为这个想法可以直接转化为您选择的语言中的递归算法，并希望我的解释足够清楚。

编辑：我知道我有点忽略了 A 可能包含重复元素的事实，但仍在考虑那部分:)

就像 - 如果您在开始排列算法之前对 A 进行排序，我认为这可能会消除重复。（还在想这个）

于 2010-08-12T13:31:05.717 回答
1

我在这里提出一个用python实现的解决方案

import itertools as it

L = ['a','b','c','d']
B = it.combinations(L,2)
swaplist = [e for e in B]
print 'List of elements to permute:' 
print swaplist
print
unique_necklaces = []
unique_necklaces.append(L)
for pair in swaplist:
    necklace = list(L)
    e1 = pair[0]
    e2 = pair[1]
    indexe1 = L.index(e1)
    indexe2 = L.index(e2)
    #swap
    necklace[indexe1],necklace[indexe2] = necklace[indexe2], necklace[indexe1]
    unique_necklaces.append(necklace)

for n in unique_necklaces:
    # Commented code display the rotation of the elements in each necklace
    print 'Necklaces'
    print n#, [n[-r:]+n[:-r]for r in (1,2,3)]

这个想法是通过两种元素的排列来构建不同的项链。对于四个元素 a、b、c、d 的列表，算法产生：

['a', 'b', 'c', 'd']
['b', 'a', 'c', 'd']
['c', 'b', 'a', 'd']
['d', 'b', 'c', 'a']
['a', 'c', 'b', 'd']
['a', 'd', 'c', 'b']
['a', 'b', 'd', 'c']
于 2014-04-08T13:15:34.090 回答
0

为了直观地理解这个问题，我认为我们可以使用这个比喻。想象墙上有一个时钟，但它不是在面上有 12 个位置，而是有 n，其中 n 是你的集合中元素的数量。

那么每个等价类只是将 A 的一个元素分配到钟面上的一个位置。

一旦分配了来自相同等价类的另一个排列，可以通过简单地旋转墙上的时钟来生成。

要生成 A 的另一个不相关排列，您需要让一个元素跳过至少一个其他元素。

现在我看到的算法将从分配开始，例如说我们在 A = {a, b, c, d} 中有四个元素，我们将它们分别分配到 12、3、6 和 9 位置以进行视觉明晰。然后我们的第一个操作是交换 a 和 b。然后是 a 和 c，然后是 a 和 d，然后我们将转到 b 并将其与位于 3 位置的元素交换，现在是 c。

这样做直到我们达到 d 会从所有等价类中生成一个代表。

这不考虑重复，但它应该比生成 A 的所有排列更有效。

于 2010-08-12T14:01:52.680 回答
0

我想到的想法是，对于任何至少有一个元素只出现一次的集合，您可以将该元素放在所有答案列表的第一个位置，然后生成其余数字的所有排列。这是一个非常简单的解决方案，因为您的第一个元素是独一无二的，通过循环移动元素确保没有等效项。显然，您生成的所有解决方案都必须是唯一的。

明显的问题是，如果你没有单一的元素，那么这将完全崩溃。我把它放进去的主要原因是因为还有其他几个解决方案不重复，我认为这个比他们更有效（解决更多案例），所以值得一提。就理解它的工作原理和实现它而言，它也非常简单。我只希望我的推理是合理的。;-)

编辑以获取更多想法：

我突然想到，这个原则可以扩展到你有一定程度的重复的情况。

如果您采用一个元素（我们现在假设它是重复的），您可以只查看它的排列以及哪些排列允许循环移位重复，就像之前假设您可以在不失一般性的情况下“锁定”一个元素。例如，如果您总共有 6 个元素并且 A 在此集合中出现两次，那么您可以拥有：

AAXXXX、AXAXXX、AXXAXX、AXXXAX、AXXXXA

最后一个与第一个（在循环移位内）相同，因此可以忽略，同上第二个和第四个。第三个（AXXAXX）可以由三个循环以返回到自身，因此具有循环的潜力。无论您循环多少次，前两个永远不会产生循环，因此您分配剩余的元素只需要确保它们是唯一的分布，并且您可以保证获得唯一的循环结果。

对于可以循环的第三种模式（AXXAXX），您需要查看元素 B 并为它们重复该过程。这次不幸的是，您将无法使用锁定第一个值的技巧来节省时间。

我不是 100% 确定你将如何将它变成一个完整的工作程序，但它是关于如何避免不得不蛮力的一些想法。

于 2010-08-12T14:15:18.957 回答