问题标签 [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.
logic - 使用 JavaScript/jQuery 生成夹具
我正在为一位同事准备一个工具,它有助于创建一个漂亮的灯具列表。我通过该工具获得了大约 2/3,收集了各种数据……然后我碰了壁。它不是一个 JavaScript 问题,而是一个数学/处理脑块。
假设我有 4 支球队,他们都需要在主场和客场比赛。使用这个工具 - http://www.fixturelist.com/ - 我可以看到有 4 支球队的主客场比赛将需要 6 周/轮/任何时间。但是,对于我的一生,我无法弄清楚这是如何以编程方式解决的。
有人可以解释处理这个的逻辑吗?
对于信息,我会使用这个现有的工具,但是我需要处理其他因素/功能,因此需要做一个自定义工作。如果我能理解如何表示这种逻辑就好了!
algorithm - 如何使用 O(1) 辅助空间将数组置换为给定的顺序?
如何实现以下OrderElements
功能?
当您可以使用线性额外空间时很容易,但是否可以只使用恒定的额外空间来完成,即直接chars
就地对元素进行排序?
PS:这不是考试题;我实际上需要这个功能。
澄清:似乎对所需的元素最终顺序存在误解。示例中的结果数组应具有以下元素,引用原始chars
数组:
这是
python - 如何检查排列是否具有相等的奇偶性?
我正在寻找一种方法来检查 2个排列(由列表表示)是否具有相同的奇偶性。请注意,我对它们是偶校验还是奇校验不感兴趣,只是相等。
我是 Python 新手,下面给出了我的幼稚解决方案作为答复。我期待 Python 大师向我展示一些很酷的技巧,以在更少、更优雅的 Python 代码中实现相同的目标。
algorithm - 快速排列 -> 数字 -> 排列映射算法
我有 n 个元素。举个例子,假设有 7 个元素,1234567。我知道有 7 个!= 这 7 个元素可能有 5040 种排列。
我想要一个包含两个函数的快速算法:
f(number) 将 0 到 5039 之间的数字映射到唯一的排列,并且
f'(permutation) 将排列映射回生成它的数字。
我不关心数字和排列之间的对应关系,只要每个排列都有自己唯一的数字。
所以,例如,我可能有函数
想到的最快算法是枚举所有排列并在两个方向上创建一个查找表,这样,一旦创建了表,f(0) 将是 O(1) 而 f('1234567') 将是在字符串上查找。但是,这会占用大量内存,尤其是当 n 变大时。
任何人都可以提出另一种可以快速运行且没有内存缺点的算法吗?
java - OCaml:两组中每个值的排列?(如何从 Java 翻译这个)
我有两组,由 Set.Make(t) 返回。我想生成两者中值的所有可能组合。我怎样才能做到这一点?
这可以生成一些对,但不是全部:
这将在Java中做到这一点:
c# - 从 C# 中的正则表达式模式生成文本的所有排列
所以我有一个正则表达式模式,我想生成该模式允许的所有文本排列。
例子:
这将返回以下字符串列表:
我的名字是史蒂夫
我的真名是史蒂夫
我的生物学名字是史蒂夫
更新: 显然,正则表达式有无限数量的匹配项,所以我只想生成可选的字符串文字,如 (?:biological|real)? 从我上面的例子。(.)* 之类的匹配项太多,因此我不会从中生成它们。
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:我不想在不需要时对值进行排序,因为这会变得太慢。
c - 枚举一组子集的排列
我有设置 S1 = {s11,s12,s13), S2 = {s21,s22,s23) 等等,直到 SN。我需要生成包含 S1,S2..SN.. 元素的所有排列,这样有每个集合中只有 1 个元素。
例如:
我的排列是:
我该怎么做呢?(我可以随机地从每个中取出 1 个并将它们合并,但在我看来,这甚至是一个坏主意)。
为了一般性,假设每个集合中有“n”个元素。我正在考虑在 C 中实现它。请注意,'N' 和 'n' 不是固定的。
python - Worker/Timeslot 置换/约束过滤算法
希望你能帮助我解决这些问题。这对工作没有帮助——它是为了一个由非常努力的志愿者组成的慈善机构,他们真的可以使用一个比他们目前拥有的更容易混淆/烦人的时间表系统。
如果有人知道一个好的第三方应用程序(当然)可以自动执行此操作,那几乎一样好。只是......请不要建议随机的时间表东西,比如预订教室的东西,因为我认为他们做不到。
提前感谢您的阅读;我知道这是一个大帖子。不过,我正在尽最大努力清楚地记录这一点,并表明我自己已经做出了努力。
问题
我需要一个工人/时隙调度算法,它为工人生成轮班,它符合以下标准:
输入数据
加工
从上面看,班次和工人是要处理的两个主要输入变量
每个班次都有所需的最小和最大工人数量。满足轮班的最低要求对成功至关重要,但如果所有其他方法都失败了,手动填充空白的轮班比“错误”要好:) 主要的算法问题是不应该有不必要的空白,当足够的时候工人可用。
理想情况下,一个班次的最大工人数量将被填补,但这是相对于其他约束的最低优先级,所以如果有什么必须给予的话,应该是这个。
灵活的约束
这些有点灵活,如果找不到“完美”的解决方案,它们的界限可以稍微扩大一点。不过,这种灵活性应该是最后的手段,而不是被随意利用。理想情况下,灵活性可以通过“fudge_factor”变量或类似变量进行配置。
- 两个班次之间有一个最短时间段。因此,例如,不应将工人安排在同一天进行两班倒。
- 一个工人在给定的时间段(比如一个月)内可以做的最大轮班次数
- 一个月内可以完成的某些班次的最大数量(例如,通宵班次)
很高兴拥有,但不是必需的
如果您能想出一个算法来完成上述操作并包含任何/所有这些,我会留下深刻的印象和感激。即使是单独执行这些位的附加脚本也会很棒。
重叠的转变。例如,最好能够指定同时发生的“前台”班次和“后台”班次。这可以通过使用不同班次数据的程序的单独调用来完成,除了在给定时间段内安排人员进行多个班次的约束将被忽略。
可在每个工人(而不是全球)基础上指定工人的最短重新安排时间。例如,如果乔感到工作过度或正在处理个人问题,或者是初学者,我们可能希望比其他工人少安排他。
当没有可用的工人适合时,一些自动/随机/公平的选择员工以填补最少轮班人数的方式。
处理突然取消的某种方式,只是填补空白而不重新安排其他班次。
输出测试
可能,该算法应该生成尽可能多的匹配解决方案,其中每个解决方案如下所示:
鉴于上述数据,这是针对单个解决方案的测试功能。我认为这是对的,但我也希望能得到一些同行评议。
尝试
我已经尝试使用遗传算法来实现这一点,但似乎无法将其调整得非常正确,因此虽然基本原理似乎适用于单班,但它甚至无法解决几个班次和几个简单的情况工人。
我最近的尝试是生成所有可能的排列作为解决方案,然后减少不符合约束的排列。这似乎工作得更快,并且让我走得更远,但我正在使用 python 2.6 的 itertools.product() 来帮助生成排列,但我不能完全正确。如果有很多错误,我不会感到惊讶,因为老实说,这个问题不太适合我的头脑:)
目前我的代码在两个文件中:models.py 和 rota.py。models.py 看起来像:
和 rota.py 看起来像:
在结果之前截取调试输出,当前给出:
algorithm - 如何最大程度地划分集合?
我正在尝试解决 Project Euler 问题之一。因此,我需要一种算法来帮助我以任何顺序找到集合中所有可能的分区。
例如,给定集合2 3 3 5
:
等等。几乎所有可能的集合成员组合。我当然在网上搜索过,但没有找到对我直接有用的东西,因为我说的是程序员语言而不是高级数学语言。
谁能帮我解决这个问题?我几乎可以阅读任何编程语言,从 BASIC 到 Haskell,所以可以用任何你喜欢的语言发帖。