问题标签 [permutation]

我正在为一位同事准备一个工具，它有助于创建一个漂亮的灯具列表。我通过该工具获得了大约 2/3，收集了各种数据……然后我碰了壁。它不是一个 JavaScript 问题，而是一个数学/处理脑块。

假设我有 4 支球队，他们都需要在主场和客场比赛。使用这个工具 - http://www.fixturelist.com/ - 我可以看到有 4 支球队的主客场比赛将需要 6 周/轮/任何时间。但是，对于我的一生，我无法弄清楚这是如何以编程方式解决的。

有人可以解释处理这个的逻辑吗？

对于信息，我会使用这个现有的工具，但是我需要处理其他因素/功能，因此需要做一个自定义工作。如果我能理解如何表示这种逻辑就好了！

如何实现以下OrderElements功能？

当您可以使用线性额外空间时很容易，但是否可以只使用恒定的额外空间来完成，即直接chars就地对元素进行排序？

PS：这不是考试题；我实际上需要这个功能。

澄清：似乎对所需的元素最终顺序存在误解。示例中的结果数组应具有以下元素，引用原始chars数组：

这是

我正在寻找一种方法来检查 2个排列（由列表表示）是否具有相同的奇偶性。请注意，我对它们是偶校验还是奇校验不感兴趣，只是相等。

我是 Python 新手，下面给出了我的幼稚解决方案作为答复。我期待 Python 大师向我展示一些很酷的技巧，以在更少、更优雅的 Python 代码中实现相同的目标。

我有 n 个元素。举个例子，假设有 7 个元素，1234567。我知道有 7 个！= 这 7 个元素可能有 5040 种排列。

我想要一个包含两个函数的快速算法：

f(number) 将 0 到 5039 之间的数字映射到唯一的排列，并且

f'(permutation) 将排列映射回生成它的数字。

我不关心数字和排列之间的对应关系，只要每个排列都有自己唯一的数字。

所以，例如，我可能有函数

想到的最快算法是枚举所有排列并在两个方向上创建一个查找表，这样，一旦创建了表，f(0) 将是 O(1) 而 f('1234567') 将是在字符串上查找。但是，这会占用大量内存，尤其是当 n 变大时。

任何人都可以提出另一种可以快速运行且没有内存缺点的算法吗？

我有两组，由 Set.Make(t) 返回。我想生成两者中值的所有可能组合。我怎样才能做到这一点？

这可以生成一些对，但不是全部：

这将在Java中做到这一点：

所以我有一个正则表达式模式，我想生成该模式允许的所有文本排列。

例子：

这将返回以下字符串列表：

我的名字是史蒂夫

我的真名是史蒂夫

我的生物学名字是史蒂夫

更新： 显然，正则表达式有无限数量的匹配项，所以我只想生成可选的字符串文字，如 (?:biological|real)? 从我上面的例子。(.)* 之类的匹配项太多，因此我不会从中生成它们。

我有一个特定范围内的数字（通常从 0 到大约 1000）。算法会从这个范围内选择一些数字（大约 3 到 10 个数字）。这种选择经常进行，我需要检查是否已经选择了所选数字的排列。

例如，一个步骤选择[1, 10, 3, 18]另一个步骤，[10, 18, 3, 1]然后第二个选择可以被丢弃，因为它是一个排列。

我需要非常快地进行这项检查。现在我将所有数组放在一个哈希图中，并使用一个自定义哈希函数：只是对所有元素求和，所以 1+10+3+18=32，还有 10+18+3+1=32。对于 equals，我使用 bitset 快速检查元素是否在两个集合中（使用 bitset 时我不需要排序，但它仅在数字范围已知且不太大时才有效）。

这可以正常工作，但会产生大量冲突，因此经常调用 equals() 方法。我想知道是否有更快的方法来检查排列？

有没有好的排列散列函数？

更新

我做了一个小基准测试：生成 0 到 6 范围内的所有数字组合，以及 1 到 9 的数组长度。有 3003 种可能的排列，一个好的散列应该生成接近这么多不同的散列（我使用 32 位数字对于哈希）：

• 仅添加 41 个不同的哈希（因此有很多冲突）
• 8 种不同的哈希值一起进行异或运算
• 286 种不同的哈希乘法
• (R + 2e) 的 3003 个不同的哈希值并按照 abc 的建议相乘（对​​ R 使用 1779033703）

所以 abc 的 hash 可以计算得非常快，而且比其他的都好很多。谢谢！

PS：我不想在不需要时对值进行排序，因为这会变得太慢。

我有设置 S1 = {s11,s12,s13), S2 = {s21,s22,s23) 等等，直到 SN。我需要生成包含 S1,S2..SN.. 元素的所有排列，这样有每个集合中只有 1 个元素。

例如：

我的排列是：

我该怎么做呢？（我可以随机地从每个中取出 1 个并将它们合并，但在我看来，这甚至是一个坏主意）。

为了一般性，假设每个集合中有“n”个元素。我正在考虑在 C 中实现它。请注意，'N' 和 'n' 不是固定的。

希望你能帮助我解决这些问题。这对工作没有帮助——它是为了一个由非常努力的志愿者组成的慈善机构，他们真的可以使用一个比他们目前拥有的更容易混淆/烦人的时间表系统。

如果有人知道一个好的第三方应用程序（当然）可以自动执行此操作，那几乎一样好。只是......请不要建议随机的时间表东西，比如预订教室的东西，因为我认为他们做不到。

提前感谢您的阅读；我知道这是一个大帖子。不过，我正在尽最大努力清楚地记录这一点，并表明我自己已经做出了努力。

问题

我需要一个工人/时隙调度算法，它为工人生成轮班，它符合以下标准：

输入数据

加工

从上面看，班次和工人是要处理的两个主要输入变量

每个班次都有所需的最小和最大工人数量。满足轮班的最低要求对成功至关重要，但如果所有其他方法都失败了，手动填充空白的轮班比“错误”要好:) 主要的算法问题是不应该有不必要的空白，当足够的时候工人可用。

理想情况下，一个班次的最大工人数量将被填补，但这是相对于其他约束的最低优先级，所以如果有什么必须给予的话，应该是这个。

灵活的约束

这些有点灵活，如果找不到“完美”的解决方案，它们的界限可以稍微扩大一点。不过，这种灵活性应该是最后的手段，而不是被随意利用。理想情况下，灵活性可以通过“fudge_factor”变量或类似变量进行配置。

• 两个班次之间有一个最短时间段。因此，例如，不应将工人安排在同一天进行两班倒。
• 一个工人在给定的时间段（比如一个月）内可以做的最大轮班次数
• 一个月内可以完成的某些班次的最大数量（例如，通宵班次）

很高兴拥有，但不是必需的

如果您能想出一个算法来完成上述操作并包含任何/所有这些，我会留下深刻的印象和感激。即使是单独执行这些位的附加脚本也会很棒。

• 重叠的转变。例如，最好能够指定同时发生的“前台”班次和“后台”班次。这可以通过使用不同班次数据的程序的单独调用来完成，除了在给定时间段内安排人员进行多个班次的约束将被忽略。

• 可在每个工人（而不是全球）基础上指定工人的最短重新安排时间。例如，如果乔感到工作过度或正在处理个人问题，或者是初学者，我们可能希望比其他工人少安排他。

• 当没有可用的工人适合时，一些自动/随机/公平的选择员工以填补最少轮班人数的方式。

• 处理突然取消的某种方式，只是填补空白而不重新安排其他班次。

输出测试

可能，该算法应该生成尽可能多的匹配解决方案，其中每个解决方案如下所示：

鉴于上述数据，这是针对单个解决方案的测试功能。我认为这是对的，但我也希望能得到一些同行评议。

尝试

我已经尝试使用遗传算法来实现这一点，但似乎无法将其调整得非常正确，因此虽然基本原理似乎适用于单班，但它甚至无法解决几个班次和几个简单的情况工人。

我最近的尝试是生成所有可能的排列作为解决方案，然后减少不符合约束的排列。这似乎工作得更快，并且让我走得更远，但我正在使用 python 2.6 的 itertools.product() 来帮助生成排列，但我不能完全正确。如果有很多错误，我不会感到惊讶，因为老实说，这个问题不太适合我的头脑:)

目前我的代码在两个文件中：models.py 和 rota.py。models.py 看起来像：

和 rota.py 看起来像：

在结果之前截取调试输出，当前给出：

我正在尝试解决 Project Euler 问题之一。因此，我需要一种算法来帮助我以任何顺序找到集合中所有可能的分区。

例如，给定集合2 3 3 5：

等等。几乎所有可能的集合成员组合。我当然在网上搜索过，但没有找到对我直接有用的东西，因为我说的是程序员语言而不是高级数学语言。

谁能帮我解决这个问题？我几乎可以阅读任何编程语言，从 BASIC 到 Haskell，所以可以用任何你喜欢的语言发帖。