c# - 找到最少使用的排列

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”，依此类推。我怀疑这行得通，但我觉得有一个更优雅的解决方案，我没有考虑过交叉连接的可能性，以便包括所有可能的组合。

有什么想法吗？

Answer 1

这里是直方图调平问题。

从这个角度考虑问题:您有一组 N 个直方图，表示值 N 个值在离散范围 {1..N} 内出现的频率。您要做的是向您的数据总体添加一组新值，使所有 直方图更接近水平。鉴于您的问题的性质，我们知道每个值总体上与其他每个值出现的次数相同。

这样做的一种方法是找出哪些值 N 在任何位置 中出现的频率最低 - 并将其分配给该位置。接下来，在剩余的直方图中，找到在任何位置出现频率最低的下一个值，并将该值分配给该位置。继续重复这个过程，直到所有的值都被分配到一个唯一的位置。这为您提供了下一组值。您现在可以迭代地重复此操作以继续生成新的值集，这些值集将尝试在每次迭代中重新平衡值的分布。

如果您在分配值时维护直方图，这将成为一个相对有效的操作(您不必经常重新扫描数据集)。

但是请记住，对于任何数量足够少的值，您总会在某种程度上“失去平衡”。没有办法解决这个问题。