是否有一个算法来生成一个多重的所有独特的环形排列？

StackOverflow https://stackoverflow.com/questions/3467914

题

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

  

有关多重集A，令P（A）表示   集合A的所有可能的排列   P（A）自然分成   分离子集是等价   类，与等价关系   是“可以通过循环移位有关。”枚举所有   这些等价类通过生成   从它们中的每恰好一个成员。

例如，考虑多重集{0，1，1，2}。的排列“0112”和“1201”是独特的排列，但后者可通过圆形移前，反之亦然找到。所需的算法不应该产生两者。

当然蛮力方法是可能的：刚刚生成的排列 - 无论圆形重复 - 使用任何的多集置换算法，以及丢弃重复发现与先前的结果相比较。然而，这往往是在实践中效率低下。所需的算法应该需要最少，如果不是零簿记。

任何见解这个问题进行了深入理解。

有帮助吗？

解决方案

泽算法

其他提示

这是稍微容易走这自下而上：

如果A只包含1个元素，P（A）还包含一种置换。 可以很容易地看到相同的作品如果A只包含2个元素。

现在，让我们假设你已经有一个所有P（A）有n个元素，并添加一个元素。 它可以以任何的n个点中的任何排列的去在P（A）。

我觉得这个想法非常转换直接向您所选择的语言递归算法，并希望我的解释是清楚。

编辑：我知道我有种被忽略的事实是一个可以包含重复的元素，但还在想着那部分：）

就像虽然 - 如果你开始置换算法排序前A，我认为这可能消除重复。 （还在想着那太）

有关问题的一个直观的了解，我认为我们可以使用这个比喻。可视化墙壁上的时钟，但而不必在脸上12点位置有n，其中n是在集合中元素的个数。

然后，每个等价类仅仅是一个在时钟面的位置A的元素的分配。

一旦被分配另一个置换从同一等价类别可以产生通过简单地在墙壁上旋转所述时钟。

要产生A的另一个不相关的置换需要有一个元素跳过至少一种其它元素。

现在我看到它会开始与例如分配算法说，我们在A = {A，B，C，d}有四个元件，我们分配它们到12，图3，图6和9的位置分别为视觉清晰度。那么，我们的第一个操作将是交换a和b。那么a和c，那么a和d，然后我们会去B和用在3位现在是c中的元素交换它。

这样做，直到我们达到d会产生从所有的等价类的代表。

此不照顾重复的，但它应比产生的所有排列更为有效。

本以为弹簧我想到的是，对于具有只出现一次，然后就可以把该元素在列表中的所有答案的第一个位置，然后生成其余的所有排列至少一个元素的任何一套数字。这是因为这样的事实的第一个元素是唯一可确保不存在由当量循环移位元件相当平凡解。那么很显然你生成解决方案必须是唯一的。

在明显的问题是，如果你没有元素单打那么这个发生故障完全。最主要的原因，我把这个是becasue有处理的没有的重复等几种解决方案，我认为这是一个比他们（解决了更多的情况下）更有效等是值得一提。它也很简单，在理解它是如何工作和实现它的术语。我只希望我的推理是合理的。 ; - ）

修改为进一步的想法：

有发生，我认为该原理可被扩展到，你必须重复到一定程度的情况。

如果你把一个元素（我们假定现在是重复的），你可以看看只是其排列，哪些将允许循环移位重复，因为assumign之前，你可以“锁定”一个到位不失一般性。例如，如果你有总共6个元件和在该组中出现两次，那么您可以有：

AAXXXX，AXAXXX，AXXAXX，AXXXAX，AXXXXA

最后的这些相同的第一个（循环移位内），所以可以忽略，同上所述第二和第四位。第三个（AXXAXX）可以通过三种循环进行，回到自身，还为自行车的潜力。前两个不能产生周期不管有多少次你循环他们，所以无论你分发剩余的元素，你只需要确保它们是唯一的分布和你保证获得通过循环的结果是唯一的。

有关该第三图案罐周期（AXXAXX）则需要看元件B，并重复该过程对于那些。这一次unfortuantely你将无法使用锁定的第一个值，以节省时间的伎俩。

我不是100％肯定，你将如何去制作成一个完全工作程序这一点，但它如何避免蛮力一些thougths。

我在这里提出用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是ALGO收率：

['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']
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top