问题标签 [permutation]

我需要制作一个随机排列列表。元素可以是任何东西，但假定它们是整数 0 到 x-1。我想制作 y 个列表，每个列表都包含 z 个元素。规则是没有列表可以包含两次相同的元素，并且在所有列表中，每个元素的使用次数相同（或尽可能接近）。例如，如果我的元素是 0,1,2,3，y 是 6，z 是 2，那么一种可能的解决方案是：

每行只有唯一的元素，没有元素被使用超过 3 次。如果 y 为 7，则 2 个元素将被使用 4 次，其余 3 次。

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

例如：

该问题提供了所有必要的数据：在给定区间[0,N-1]内生成K个非重复整数序列的有效算法是什么。如果K很大并且足够接近N，那么简单的算法（生成随机数并在将它们添加到序列之前查找它们以查看它们是否已经存在）非常昂贵。

有效地从链表中选择一组随机元素中提供的算法似乎比必要的复杂，并且需要一些实现。我刚刚发现另一种算法似乎可以很好地完成这项工作，只要您知道所有相关参数，一次通过。

受此问题和答案的启发，如何在 F# 中创建通用排列算法？谷歌没有给出任何有用的答案。

编辑：我在下面提供了我的最佳答案，但我怀疑托马斯的更好（当然更短！）

给定以下示例数组，我怎样才能找到所有可用时间的排列，以便满足 amountNeeded？换句话说，跟随数组应该产生以下内容：

使用资源 10 和 13 于 2008 年 5 月 14 日 08:00 至 08:10 可用

使用资源 10 和 13 于 2008 年 5 月 14 日 08:10 至 08:20 可用

我有一个元素数组 ( arr) 和一个函数 ( f)，它接受 2 个元素并返回一个数字。

我需要数组的排列，这样对于每个inf(arr[i], arr[i+1])尽可能少。（它应该循环，即它也应该最小化）iarrf(arr[arr.length - 1], arr[0])

此外，f工作有点像距离，所以f(a,b) == f(b,a)

如果效率太低，我不需要最佳解决方案，但是一个运行合理且速度快的解决方案，因为我需要实时计算它们（我不知道长度arr是多少，但我认为它可能是大约30）

我一直对算法、排序、加密、二叉树、数据压缩、内存操作等感兴趣。

我用 STL 函数 next_perm() 阅读了 Mark Nelson 关于 C++ 中排列的文章，非常有趣和有用，之后我编写了一个类方法来在 Delphi 中获取下一个排列，因为这是我目前使用最多的工具。这个函数适用于字典顺序，我从stackoverflow上另一个主题的答案中得到了算法的想法，但现在我遇到了一个大问题。我正在处理向量中重复元素的排列，并且有很多我不需要的排列。例如，我有 7 个元素的第一个排列（按字典顺序）：

6667778（6 = 连续 3 次，7 = 连续 3 次）

对于我的工作，我认为有效的烫发只有那些最多连续重复 2 个元素的烫发，如下所示：

6676778（6 = 连续 2 次，7 = 连续 2 次）

简而言之，我需要一个函数，该函数根据收到的参数仅返回最多具有 N 个连续重复的排列。

有谁知道是否有一些算法已经这样做了？

很抱歉文本中的任何错误，我仍然不会说英语。

非常感谢，卡洛斯

我从来没有太多的数学，我希望有人可以帮助我解决以下问题。

我有5个盒子：

这些框可以是白色、灰色或黑色（或将其视为 0、1、2）

盒子集合可以有多少种可能的状态？

生成所有可能结果的伪代码（或任何语言）是什么？

IE...

等等等等……

我真的很感谢任何人可以为此提供的任何帮助。

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

因此，运行是排列中有序且有序的一组连续数字。在列表中，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]是一次运行，因此可以进一步减少。这就是它无效的原因。该顺序将在另一个算法的进一步操作中很重要，但可以在最后扩展各个元素以挽救原始排列。

我在 Java 中有一个资源调度问题，需要对事物进行排序，但是对于哪些资源可以彼此相邻存在限制。一个很好的类比是一串“数字”，其中只有某些数字可以彼此相邻。我的解决方案是递归的，适用于小字符串，但运行时间为 O(X^N)，其中 X 是可能的位数（基数），N 是字符串的长度。它很快变得无法管理。

使用下面的兼容性矩阵，这里有一些允许字符串的示例
长度为 1：0、1、2、3、4
长度为 2：02、03、14、20、30、41
长度为 3：020、030、 141、202、203、302、303、414

我计算所有长度为 N 的字符串的解决方案是从一个空字符串开始，置换第一个数字，然后递归调用所有长度为 N-1 的字符串。递归调用检查添加的最后一个数字并尝试该数字旁边的所有排列。进行了一些优化，因此我不会每次都尝试置换 00、01、04，例如 - 只有 02、03，但性能仍然很差，因为它从基数 5（示例）扩展到基数 4000。

除了尝试枚举所有排列之外，还有什么更好的方法来计算排列吗？