问题标签 [necklaces]

长度为 n 的 k-ary 项链是长度为 n 的有序列表，其项目来自长度为 k 的字母表，它是所有列表中共享旋转排序的排序中的字典第一个列表。

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

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

我想在 Scheme（或您选择的 Lisp）中生成这些。我找到了一些论文...
Savage - A New Algorithm for Generate Necklaces
Sawada - 在恒定摊销时间内生成手链
Sawada - 生成带有禁止子串的项链
...但是其中提供的代码对我来说是不透明的。主要是因为它们似乎没有传递所需的字母或长度（n）。我正在寻找的方案程序的形式是 (necklaces n '(ab c...))。

我可以通过首先生成 k^n 列表然后过滤掉旋转来轻松生成这些。但它的内存效率非常低......

谢谢！

一些背景：我正在编写一个或多或少的蛮力搜索算法来解决我遇到的问题。为了做到这一点，我需要生成和评估所有可能性，以找出最好的。由于评估实际上需要一些时间，我希望生成尽可能少的解决方案，以完全覆盖我的搜索空间。此外，我能做的元素越多越好。对于任何数字 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(Script)、Python、Ruby、Lisp/Scheme）。

对于有兴趣的人：这是仅获取我迄今为止拥有的唯一排列的算法：

• 如果你有 N-1 和 M 的所有排列，那么你可以通过将 e1 插入它们来使用它们来找到 N 和 M 的排列。你不能只是到处插入，因为那样你会得到重复。我不知道为什么会这样，但你可以计算出从旧的可能性中产生的新可能性的数量（我称之为“增益”）。对于第一个旧排列，这个数字从 M+1 开始，对于每个旧排列减一，直到它变为零，此时它又回到 M 等（仅当 M>=N 时才有效）。因此，如果您想计算 N=3 和 M=3 的排列，并且您有 N=2 和 M=3 的 10 个排列，它们的增益将是 [4 3 2 1 3 2 1 2 1 1]。

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

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

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

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

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