标签: necklaces

I encountered this problem when doing some enthusiastic programming. The problem can be expressed as follows:

For a multiset A, let P(A) denote the set of all possible permutations of A. P(A) is naturally divided into disjoint subsets that are equivalence classes, with the equivalence relation being "can be related by circular shifts." Enumerate all these equivalence classes by generating exactly one member from each of them.

例如,考虑多集{0,1,1,2}.排列"0112"和"1201"是唯一的排列,但后者可以通过对前者进行循环移位来找到,反之亦然.所需的算法不应生成两者.

当然,蛮力方法是可能的:只需生成排列 - 无论循环重复 - 使用任何多重排列算法,并丢弃与先前结果相比较的重复.然而,这在实践中往往效率低下.如果不是零记账,所需算法应该要求最少.

深刻理解对此问题的任何见解.

一些背景:我正在编写或多或少的强力搜索算法来解决我遇到的问题.为了做到这一点,我需要生成并评估所有可能性,以找出哪个是最好的.由于评估实际上需要一些时间,我宁愿尽可能少地生成完全覆盖我的搜索空间的解决方案.此外,我可以做的更多元素越多越好.对于任何数字K,通常有K!对于高于~10的数字,排列和生成它们都很难.

真正的问题:搜索空间应包含两个元素的所有排列(N次el1和M乘以el2,其中K = M + N),具有以下限制:

1. 他们必须是独一无二的(即我只想要[aabbb]一次)
2. 我不需要任何排列的反转(即如果我有[aab],我也不需要[baa])
3. 我认为排列是圆形的,所以[aab] = [aba] = [baa]

如果我能够做到这一点,可能性的数量将大大减少.由于理想情况下K很大,因此首先生成所有排列然后根据这些标准过滤它们是不可行的.我已经完成了第一个限制(见下文),它将Matlab的正常排列函数(perms)的数量从2 ^ K减少到K!/ N!M !,这是一个巨大的胜利.第二个限制只会将可能性的数量减少一半(在最好的情况下),但我认为第三个也应该能够真正减少可能性的数量.

如果有人知道怎么做,最好还有如何计算会有多少种可能性,这对我有很大的帮助!我更喜欢解释,但代码也很好(我可以读C语言,Java(脚本),Python,Ruby,Lisp/Scheme).

对于感兴趣的:这是迄今为止我只获得唯一排列的算法:

function genPossibilities(n, m, e1, e2)
     if n == 0
         return array of m e2's
     else
         possibilities = genPossibilities(n-1, m, e1, e2)
         for every possibility:
             gain = number of new possibilities we'll get for this smaller possibility*
             for i in max(0,(m+n-gain))
                 if possibility(i) is not e1
                     add possiblity with e1 inserted in position i
         return new possibilities

• 如果您有N-1和M的所有排列,那么您可以使用它们通过将e1插入其中来查找N和M的排列.你不能只是在任何地方插入,因为那样你就会得到重复.我不知道为什么会这样,但你可以计算出你从旧的可能性中产生的新可能性的数量(我称之为"增益").对于第一个旧排列,该数字从M + 1开始,并且对于每个旧排列减少一个,直到它变为零,此时它返回到M等等(仅当M> = …

长度为n的k-ary项链是长度为n的有序列表,其项目是从长度为k的字母表中绘制的,这是按字典顺序排列的第一个列表,在所有列表中共享旋转下的排序.

示例:(1 2 3)和(1 3 2)是字母{1 2 3}中长度为3的项链.

更多信息:http: //en.wikipedia.org/wiki/Necklace_(bizbinicsics)

我想在Scheme(或你选择的Lisp)中生成这些.我找到了一些论文......
野人 - 一种生成项目的新算法
Sawada - 在恒定摊销时间生成手镯
Sawada - 生成带有禁止的子串的项链
......但是它们中的代码对我来说是不透明的.主要是因为他们似乎没有传递字母或所需的长度(n).我正在寻找的方案程序是形式(项链n'(ab c ...)).

通过首先生成k ^ n个列表然后过滤掉旋转,我可以很容易地生成这些.但它的内存效率非常低......

谢谢!