问题标签 [permutation]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
1 回答
1413 浏览

logic - 使用 JavaScript/jQuery 生成夹具

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

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

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

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

0 投票
6 回答
1490 浏览

algorithm - 如何使用 O(1) 辅助空间将数组置换为给定的顺序?

如何实现以下OrderElements功能?

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

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

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

这是

0 投票
8 回答
5005 浏览

python - 如何检查排列是否具有相等的奇偶性?

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

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

0 投票
12 回答
44207 浏览

algorithm - 快速排列 -> 数字 -> 排列映射算法

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

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

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

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

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

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

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

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

0 投票
3 回答
2303 浏览

java - OCaml:两组中每个值的排列?(如何从 Java 翻译这个)

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

这可以生成一些对,但不是全部:

这将在Java中做到这一点:

0 投票
3 回答
2024 浏览

c# - 从 C# 中的正则表达式模式生成文本的所有排列

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

例子:

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

我的名字是史蒂夫

我的真名是史蒂夫

我的生物学名字是史蒂夫

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

0 投票
7 回答
7867 浏览

performance - 用于排列的良好哈希函数?

我有一个特定范围内的数字(通常从 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:我不想在不需要时对值进行排序,因为这会变得太慢。

0 投票
7 回答
1548 浏览

c - 枚举一组子集的排列

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

例如:

我的排列是:

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

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

0 投票
3 回答
3422 浏览

python - Worker/Timeslot 置换/约束过滤算法

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

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

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

问题

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

输入数据

加工

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

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

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

灵活的约束

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

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

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

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

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

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

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

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

输出测试

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

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

尝试

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

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

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

和 rota.py 看起来像:

在结果之前截取调试输出,当前给出:

0 投票
6 回答
1382 浏览

algorithm - 如何最大程度地划分集合?

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

例如,给定集合2 3 3 5

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

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