是否有一个算法来生成一个多重集的所有唯一循环置换?

Sawada's algorithm

这种自下而上的方式稍微容易一些:

现在,假设你已经有了n个元素的A的所有P(A),并且你添加了一个元素。 它可以进入P(A)中任意排列的n个点中的任意一个。

我认为这个想法相当直接地转化为您选择的语言中的递归算法,希望我的解释足够清楚。

不过,如果在开始排列算法之前对a进行排序,我认为这可能会消除重复项(还在想这个)

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']

那么每个等价类只是一个元素在时钟面上的一个位置的赋值。

现在我看到的算法是从一个赋值开始,比如说我们在A={A,b,c,d}中有四个元素,为了视觉上的清晰,我们把它们分别赋给12,3,6和9个位置。那么我们的第一个行动就是交换a和b。然后a和c,然后a和d,然后我们去b,把它和3位置的元素交换,现在是c。

在我们到达d之前这样做将从所有等价类中生成一个代表。

这不需要处理重复项,但它应该比生成A的所有排列更有效。

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

显而易见的问题是,如果您没有单独的元素,那么这将完全崩溃。我把这个放进去的主要原因是因为还有其他几种解决方案 不 重复,我认为这一个是比他们更有效(解决更多的情况),所以值得一提。就理解它的工作原理和实现而言,它也相当简单。我只希望我的推理是正确的

编辑以供进一步思考:

我突然想到,这个原则可以推广到你有一定程度的重复的情况。

AAXXXX,axxx,AXXAXX,AXXXAX,AXXXXA

最后一个与第一个相同(在循环移位中),因此可以忽略,第二个和第四个也是如此。第三个(AXXAXX)可以循环三次以恢复自身,因此具有循环的潜力。前两个永远不会产生循环,不管你循环了多少次,所以不管你如何分配其余的元素,你只需要确保他们是唯一的分布,你保证得到唯一的循环结果。

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

我不是100%确定你将如何把它变成一个完全有效的程序,但它是一些关于如何避免暴力的想法。