问题标签 [combinatorics]

如何在 Python 中生成列表的所有排列，而与列表中元素的类型无关？

例如：

我正在尝试帮助某人编写一个我认为很容易的程序，但当然它从来都不是:)

我正在尝试制定班级名册（通常在 10 到 20 名学生之间），并有效地将每个同学与另一个同学配对，以组成独特的小组。因此，在一个 10 人的班级中，您可以有 9 个小组。

它也需要能够处理奇数个学生，这增加了我的困惑。

我正在考虑在 Java 中执行此操作，但这很灵活。关于算法方式的任何想法，以保证 a) 不是无限循环（以 2 个已经成为合作伙伴的人结束）和 b) 我的目标是时间比空间更有效，因为班级规模会很小！

谢谢！

我希望这种方法适用于任何给定数量的参数，我可以通过代码生成来做到这一点（有很多丑陋的代码），它可以通过递归来完成吗？如果是这样怎么办？我理解递归，但我不知道如何写这个。

长度为 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 列表然后过滤掉旋转来轻松生成这些。但它的内存效率非常低......

谢谢！

我正在寻找一种算法来生成一组排列，这样我就可以在 Clojure 中制作一个惰性列表。即我想遍历一个排列列表，其中每个排列在我请求之前不会计算，并且所有排列不必一次存储在内存中。

或者，我正在寻找一种算法，在给定某个集合的情况下，它将返回该集合的“下一个”排列，这样在它自己的输出上重复调用该函数将循环遍历原始集合的所有排列，在一些顺序（顺序是什么无关紧要）。

有这样的算法吗？我见过的大多数排列生成算法都倾向于一次生成它们（通常是递归的），这不能扩展到非常大的集合。Clojure（或其他函数式语言）中的实现会有所帮助，但我可以从伪代码中弄清楚。

我需要一种算法，可以将排列中的运行映射到单个数字，但也可以减少后续数字。

因此，运行是排列中有序且有序的一组连续数字。在列表中，1;2;3;5;6;4 有两个运行，1;2;3 和 5;6。我想用一个数字替换这些，最少，所以如果在删除运行后，我们有 4 个元素的排列，排列使用数字 1 ... 4。在上面，我们必须减少两次运行. 第一次运行将是 1，4 转换为 2，[5;6] 转换为 3，以保持第二个标准。如果我对减少的排列进行排序，然后从映射中扩展内部元素，并对原始排列进行排序，我将得到相同的结果。结果的排列不应该有任何运行。

例如（我已经突出显示了运行）：

现在，我正在传递列表并制作列表列表，对运行进行分组。实际上，第二部分是制作干净解决方案的困难部分。我想到了天真的方法，很好奇是否有人有一些聪明的技巧可以做得比我的更好，我就像 O(2n + n log n)，

• 用运行的头元素替换运行并将该数据插入哈希表（用于可恢复性）
• 排序以使用其排序索引创建缺失数字的映射。[1;6;5;4] 将输出 [(1,1);(4,2);(5,3);(6,4)]
• 将步骤 1 中的列表替换为步骤 2 中创建的地图并更新哈希表以进行翻译。

再次运行一个例子：

如果我对这个排列进行排序并重构：[1;2;3;4], 3->3;4 和 4->5;6 我得到 1;2;3;4;5;6。也排序了。

我正在使用列表，因此首选功能方法。无需代码。当然，欢迎所有想法。

编辑：

默维尔登：

我不清楚映射的精确条件是什么。为什么不允许只为具有 N 次运行的排列生成排列 [1,2,...,N]？您似乎更喜欢将运行映射到该运行的数字，但是（因为这并不总是可能的）您似乎允许一些自由。–

我不喜欢将一个运行映射到该运行中的一个数字（见上图！），但我需要保留一个ordering。排列 [1;2;3...N]是一次运行，因此可以进一步减少。这就是它无效的原因。该顺序将在另一个算法的进一步操作中很重要，但可以在最后扩展各个元素以挽救原始排列。

我正在寻找一种方法来生成按单个属性排序的对象组合。我不认为字典顺序是我正在寻找的......我会尝试举一个例子。假设我有一个对象 A、B、C、D 的列表，其中我想要按 3、3、2、1 排序的属性值。这给出了 A3、B3、C2、D1 对象。现在我想生成 2 个对象的组合，但它们需要按降序排列：

• A3 B3
• A3 C2
• B3 C2
• A3 D1
• B3 D1
• C2 D1

生成所有组合并对它们进行排序是不可接受的，因为现实世界的场景涉及大集合和数百万个组合。（40 个，8 个订单），我只需要高于特定阈值的组合。

实际上，我需要按给定属性的总和分组的阈值以上的组合计数，但我认为这样做要困难得多 - 所以我会满足于开发高于阈值的所有组合并计算它们。如果有可能的话。

编辑 - 我最初的问题不是很精确......我实际上并不需要订购这些组合，只是认为它有助于隔离高于阈值的组合。更准确地说，在上面的例子中，给定阈值 5，我正在寻找一个信息，即给定集合产生 1 个总和为 6 ( A3 B3 ) 和 2 总和为 5 ( A3 C2, B3 C2)。我实际上并不需要组合本身。

我正在研究子集和问题，但如果我正确理解给定的动态解决方案，它只会给你信息是否有给定的总和，而不是总和的计数。

谢谢

不确定该示例（也不是实际用例）是否符合 NP-Complete 的条件，但我想知道最 Pythonic 的方式来执行以下操作，假设这是可用的算法。

说你有：

以及一些需要一组人员的操作。（这里的关键值是 Person 是快乐还是悲伤。）

因此，给定 PersonA、PersonB、PersonC、PersonD - 我想最终列出可能的 2**4 个悲伤和快乐人物组合的列表。IE

有没有一种很好的 Pythonic 方式来做到这一点？我在考虑列表推导（并修改对象以便您可以调用它并返回两个对象，true 和 false），但我看到的推导格式需要我提前知道 Persons 的数量。我想独立于人数来做到这一点。

编辑：假设我要运行的那个操作是一个更大的问题集的一部分——我们需要测试给定集的所有 Person 值以解决我们的问题。（即我知道这现在看起来不是 NP-complete =））有什么想法吗？

谢谢！

出于没有特别的原因，我决定寻找一种算法，该算法可以产生 1...n 之间的所有可能的 k 整数选择，其中 k 整数之间的顺序无关紧要（n 选择 k 事物）。

出于完全相同的原因，这根本不是原因，我也在 C# 中实现了它。我的问题是：

您在我的算法或代码中看到任何错误吗？而且，更重要的是，你能推荐一个更好的算法吗？

请更多地关注算法而不是代码本身。这不是我写过的最漂亮的代码，但如果你看到错误，请告诉我。

编辑： Alogirthm 解释-

• 我们持有 k 个指数。
• 这会创建 k 个嵌套的 for循环，其中循环 i 的索引是 indices[i]。
• 它模拟 k for循环，其中 indices[i+1] 属于嵌套在 indices[i] 循环中的循环。
• indices[i] 从 indices[i - 1] + 1 运行到 n - k + i + 1。

代码：

我为这个冗长的问题道歉，它可能适合博客文章，但我确实希望社区的意见在这里。

谢谢，
阿萨夫

给定一个大小为 n 的集合 S，它被划分为大小为 n1,..,nk 的类 (s1,..,sk)。自然地，它认为 n = n1+...+nk。

我有兴趣找出可以组合此分区元素的方法的数量，以便每个组合恰好包含每个类的一个元素。

因为我可以从 s1 中选择 n1 个元素，从 s2 中选择 n2 个元素，依此类推，所以我正在为任意 n1,..nk 寻找 max(n1*..*nk) 的解决方案，它持有 n1+..+nk =n。

我感觉这是一个线性优化问题，但是自从我作为本科生学习这些东西以来已经太久了。我希望有人记得如何计算这个。