寻找最少使用的排列

Question

我需要根据历史数据均匀分配一组数据，以便每个数字在时间的每个位置上都出现相等（或接近相等）次数。问题是，给定过去使用的订购列表，看起来像这样（但可能有任意数量的元素）：

1,2,5,3,4
4,1,5,2,3
1,3,5,2,4
4,1,2,3,5
2,4,1,3,5
5,1,4,3,2
1,5,3,2,4
5,1,3,2,4
3,2,5,4,1
4,3,1,5,2

我该如何找到使用最少且会导致“更平衡”排序集合的值的排序方式。显而易见的答案是通过分组并计数，选择最少使用的一种，但问题在于最少使用的排列可能从未被使用过，例如，在这里，“1,2,3,4,5”的排序是最少使用的候选，因为它根本没有出现过。

简单的答案似乎是确定“1”出现的最频繁的位置，并将该位置设置为“1”，然后对每个数字依此类推。我认为这样可以解决问题，但我觉得还有一个更优雅的解决方案，即通过交叉连接来考虑所有可能的组合。

有什么想法吗？

- powlette

---

为什么“1,2,3,4,5”不好呢？感觉你想要“随机性”，但这是一个相当主观的事情。你的想法行不通，因为如果1和3的最小位置相同怎么办？总之，只需生成随机排列-迟早你会均匀地对它们进行采样 ;) - Random Dev

“任意数量的元素”使得你的问题基本上是不可能解决的。如果有n个元素，则有n!种排列方式。对于n=5，只有120种可能性，但对于n=15，有超过一万亿种可能性。除非你的数据集中有多达数万亿个项目，否则几乎所有这些可能的排列方式都不会在数据集中有任何示例。” - Eric Lippert

生成的数字需要是随机的吗？我发现按顺序生成的数字在时间上分布均匀。 - David Chan

我不应该说“任意数量的元素” - 任何时候总数不会超过10个。我同意随机选择顺序是好的，但问题是，它需要在长期和短期内均匀分布。每次选择都需要尽可能地使其更加平衡，因为我们不能等待它在长期内平衡。 - powlette

也许可以持续记录到目前为止的“平均”排序，并且每次想要将新的排序添加到列表中时，您可以找到距离平均值最远的排序。为此，您可以使用欧几里得距离和贪心选择差异最大的匹配元素的启发式方法...因此，如果1,2,3的数字的平均值为(1.2, 2.3, 2.5)，则最佳选择是(3, 2, 1)，其平方距离为5.58...我认为这将是摊销O(k^3 n)，其中k = 5，n是您添加的新排序数量。 - Patrick87

Answer 1

这里的问题是直方图均衡化。

从这个角度考虑问题：你有一组N个直方图，表示离散范围{1..N}内N个值出现频率。你想要做的是添加一个新的数据集，将所有直方图都转换为更平坦的状态。鉴于你的问题的性质，我们知道每个值总体上将与其他值出现相同的次数。

一种解决方法是找出N中在任何位置出现频率最低的值，并将其分配到该位置。接下来，在剩余的直方图中，找到下一个在任何位置出现频率最低的值，并将该值分配到该位置。继续重复此过程，直到所有值都被分配了唯一的位置。这给你提供了下一个数据集。现在，你可以迭代地重复这个步骤，以生成尝试使用每次迭代重新平衡值分布的新值集。

如果在分发值时保留直方图，这将变成一个相对高效的操作（你不必不断重新扫描数据集）。

请记住，对于任何足够小的值人口，您总是会在某种程度上“失衡”。这是无法避免的。

- LBushkin

Answer 2

我假设你有一种生成随机排列的方法（例如在C#中随机“排序”（洗牌）整数列表的最有效方法）。鉴于此，以下是一些建议来生成单个新的排序：

1）生成两个随机排列

2）保留其中一个可以使不平衡最小化的排列。

平衡的一种度量方式是将每个位置上数字频率的计数列表视为向量，在完美平衡的情况下，每个元素都相同。然后，通过从两个随机排列中选择，您将选择一个排列，其平均向量指向与当前不平衡方向相反的方向，因此您应该倾向于在仍然产生随机排列序列的同时进行纠正。

- mcdowella

Answer 3

如果组合的总数足够小，那么我曾经在类似问题上使用过一种方法：

维护一个选择池，定期补充。

在您的示例中，有120个可能的排列。制作一个由120个元素组成的数组，为每个元素分配一个初始值，比如5。当您需要一个随机值时，从这个池中选择，箱子中的数字是给予该箱子的权重。（开始时，箱子总和为600。从1到600中选择一个随机数，减去箱子直到<=0。您刚才减去的箱子就是您的结果。）当选取一个条目时，将该箱子减少一个。一旦您从堆中进行了120次抽取，就向每个箱子添加1。

显然，如果可能性的总数太高，这变得不切实际。

- Loren Pechtel