有没有一种算法可以生成一个多重集合的所有唯一循环排列？

Question

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

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

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

当然，一种暴力的方法是可能的：使用任何多重集排列算法生成排列，无视循环重复，并通过与先前结果进行比较来丢弃重复项。然而，在实践中，这种方法往往效率低下。所需的算法应该需要最少的，如果有的话，则需要零的簿记。

非常感谢您对这个问题的任何见解。

- Cong Ma

Answer 1

Sawada算法

- sdcvvc

---

感谢提供链接和Sawada论文的参考。我会花些时间研究它，如果有进一步的问题会再次发布。 - Cong Ma

好的，我会将其标记为解决方案 :)我还发现了一篇关于算法的论文，它与一个紧密相关的问题有关，即从字母表中生成特定长度的所有项链。论文链接：http://dx.doi.org/10.1006/jagm.2000.1108 - Cong Ma

Answer 2

我在这里提出一个用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']

- Jean-Pat

---

我认为答案不正确，因为只应该有4!/4=6种情况，但你得到了7种情况！ - Wei Shan Lee

Answer 3

从底向上来说，这个问题稍微容易一些：

如果A只包含一个元素，那么P(A)也只包含一个排列。 很容易看出，如果A只包含两个元素，同样适用。

现在，假设你已经有了所有包含n个元素的A的P(A)，然后再添加一个元素。 它可以放在P(A)中任意一个排列的任意一个位置。

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

编辑：我知道我有点忽略了A可能包含重复元素的事实，但我还在思考这部分内容 :)

只是一个想法 - 如果在开始排列算法之前对A进行排序，我认为这可能会消除重复项。（对此也在思考）

- Yoni H

Answer 4

为了直观地理解这个问题，我认为我们可以采用这个比喻。想象一下墙上的时钟，但是它的表盘不是有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的所有排列更有效。

- Shane Hogan

---

谢谢回复。实际上，在我在这里发布问题之前，这就是我简要考虑过的内容。由于某种原因，我忘记了它，而选择了愚蠢的“生成所有排列”：p。正如你所说，它仅适用于集合A是没有重复成员的“普通”集合，但仍然是理解问题的良好起点。 - Cong Ma

Answer 5

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

显而易见的问题是，如果您没有单个元素，则完全无法解决此问题。我之所以提出这个问题，是因为还有其他几种解决方案处理没有重复项的情况，我认为这种方法比它们更有效（解决更多情况），因此值得一提。从实现和理解工作原理的角度来看，这也非常简单。我只希望我的推理是正确的。 ;-)

进一步思考的编辑：

我意识到，这个原则可以在某种程度上扩展到具有重复项的情况。

如果您选择一个元素（我们现在假设该元素重复），则可以仅查看其排列，并确定哪些排列允许循环移位重复，就像先前假设您可以“锁定”其中一个元素一样。例如，如果您有6个元素，其中A在该集合中出现两次，则可以

AAXXXX，AXAXXX，AXXAXX，AXXXAX，AXXXXA

其中最后一个（AXXXXA）与第一个相同（在循环移位内），因此可以忽略，第二个和第四个也是如此。第三个（AXXAXX）可以通过循环三次得到自身，因此具有循环的潜力。无论您将第一个和第二个循环多少次，它们都永远不会产生循环，因此无论您如何分配剩余元素，您只需要确保它们是唯一的分配方式，就可以保证通过循环得到唯一的结果。

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

我不确定如何将其转化为完全可工作的程序，但这是一些避免强制执行的想法。

- Chris