问题标签 [permutation]

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

是否有使用排列和排列组实现操作的 C++ 模板类？这样的类必须实现求积和求逆、乘法等。

我有一个未知长度的数组，它总是有一个可整除的值，例如：

我需要创建集合：

值的顺序除以 v 表示它们是一个集合。集合中值的顺序无关紧要（我随机将它们放在一起）。如您所见，在任何其他集合或同一集合中不能有重复的集合匹配。

我尝试了许多不同的方法来想出一些可行的方法。我得到的最接近的是将初始值放入包含所有可能的有效匹配的级联数组中：

这些值是一个名为 $sched 的数组中的数组。 我在数组中留下了 30 个 .. 哎呀

数字是团队。每支球队都需要与每支球队比赛一次。赛程将设置为每支球队每周只打一场比赛。时间表需要设置几个星期，以允许在没有球队每周比赛超过一次的情况下进行所有比赛。

我已经使用了一个排列函数，这就是我想出上面没有相同匹配的数组的方法。我现在需要弄清楚如何输出时间表，如上面的 Sets 所示。（请记住，只要没有球队在同一组比赛中两次比赛，示例的顺序并不重要）

所以这没有用，我把它复杂化了，超出了它应该的程度，我不能再解决这个问题了。任何帮助，即使它意味着重新开始，将不胜感激！

我有兴趣计算如下参数的排列：

所以我可以写类似 List getPermutations(); 这样我就可以获得每部电影的列表。我对支持多种数据类型感兴趣。

谁能指出我正确的方向来构建注释和 List getPermutations() 方法？

我正在寻找一种算法，该算法将采用数字或单词并找到它们的所有可能变体，并让我定义要一起查找的值的数量。

示例可以说字符串或数组是：

那么值为 2 的结果可能是：

因此，这组 3 个项目的结果是 6 个可能的变体，其中 2 个结果
与 3 个匹配结果匹配：

...甚至可能有更多选择

我在 Stackoverflow 上找到了这个示例的链接，但它是在 javascript 中，我想知道是否有人知道如何在 PHP 中执行此操作，也许已经构建了一些东西？

http://www.merriampark.com/comb.htm（死链接）

我有一组 N^2 个数字和 N 个 bin。每个 bin 应该具有分配给它的集合中的 N 个数字。我面临的问题是找到一组将数字映射到 bin 的分布，满足约束条件，即每对数字只能共享同一个 bin 一次。

分布可以很好地用 NxN 矩阵表示，其中每一行代表一个 bin。然后问题是找到矩阵元素的一组排列，其中每对数字仅共享同一行一次。它是哪一行无关紧要，只是两个数字都分配给了同一个数字。

满足 N=8 约束的 3 个排列示例集：

不属于上述集合的排列：

由于与第二个排列有多次冲突，例如，因为它们都将数字 0 和 32 配对在一行中。

枚举三个很容易，它由 1 个任意排列、它的转置和一个矩阵组成，其中行由前一个矩阵的对角线组成。

我找不到一种方法来制作一个包含更多内容的集合。这似乎是一个非常复杂的问题，或者是一个没有明显解决方案的简单问题。无论哪种方式，如果有人对如何在合理的时间内解决 N=8 案例有任何想法，或者确定问题的正确学术名称，我将不胜感激，这样我就可以用谷歌搜索它。

如果您想知道它有什么用，我正在寻找一种用于具有 8 个缓冲区的交叉开关的调度算法，该算法为 64 个目的地的流量提供服务。这部分调度算法与输入流量无关，并在多个硬连线的目标缓冲区映射之间循环切换。目标是让每对目标地址在循环周期内只竞争一次相同的缓冲区，并最大化该周期的长度。换句话说，让每对地址尽可能少地竞争同一个缓冲区。

编辑：

这是我的一些代码。 代码

它是贪婪的，它通常在找到第三个排列后终止。但是应该存在一组至少 N 个排列满足该问题。

另一种方法是要求选择排列 I 涉及寻找排列 (I+1..N)，以检查排列 I 是否是由最大排列数组成的解决方案的一部分。这需要枚举所有排列以在每一步检查，这非常昂贵。

考虑以下情况。

我有一个数字数组：

如果加入了这个数组，我将拥有数字1234。

我想交换数字以达到最接近的更高数字。

1234将变为1243，将变为1324，将变为1342等等。

我需要使用什么算法来在数组中进行这些更改？

理想情况下，我想以这种方式使用该算法：（假设 Array 将此算法作为一个称为演练的函数）

数字列表继续：

1234
1243
1324
1342
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241

我想写一个 ruby​​ 片段，它需要一个字符串并输出所有可能的大写排列。基本上，我有一个我记得的密码，但我不记得它是如何大写的。

到目前为止，我有以下内容：

这工作得很好，但我想知道是否有任何 ruby​​ists 可以帮助我改进它，这样它就不必在带有数字的字符串上不必要地工作。

例如，字符串“tst1”生成：

我正在寻找的输出是：

有任何想法吗？

来自维基百科：

字典顺序生成

对于每个数字 k，0 ≤ k < n!，以下算法生成初始序列 sj, j = 1, ..., n 的相应词典排列：

这背后的逻辑是什么？它是如何工作的？？