均匀地分配列表中的所有项目

Question

我有一段时间遇到这个问题,仍然在尝试解决方案.

在列表中均匀分配项目的最佳方法是什么,差异很小？

假设我们在数组中有一个列表或元素:

Red, Red, Red, Red, Red, Blue, Blue, Blue, Green, Green, Green, Yellow

理想情况下,输出会产生类似于:

Red, Blue, Red, Green, Red, Yellow, Blue, Red, Green, Red, Blue, Green.

每个实例尽可能"远离"自身的另一个实例......

当我第一次尝试尝试解决这个问题时,我必须承认我天真,所以我只是使用某种形式的种子随机数来洗牌,但这会导致实例聚集.

建议从频率最高的项目开始,因此红色将被置于n*12/5的位置,n为0到4(包括0和4).

然后将下一个最重复的元素(蓝色)放置在n*12/3 + 1的位置,n为0到2(包括0和2).如果已经有东西放在那里,只需把它放在下一个空位.然而,当它在纸上记录时,这并不适用于所有情况,

说清单是唯一的

Red, Red, Red, Red, Red, Blue

它会失败.

其中任一选项有三个相同颜色的邻接

Red, Red, Blue, Red, Red, Red
Red, Red, Red, Blue, Red, Red

所以,任何想法或实现如何做到这一点将是非常棒的.

如果重要的是我正在研究objective-c,但现在我关心的是如何做到这一点的方法.

Answer 1

只是一个简单的想法:为每种类型的项目使用单独的列表.然后使用类似合并排序的东西将每个列表中的一个项目插入到新列表中,始终以相同的顺序排列.跳过空列表.

这当然不会产生完美的解决方案,但它很容易实现,而且应该很快.一个简单的改进是按大小排序列表,最大的是.这比列表的随机顺序提供了稍好的结果.

更新:也许这可以使它变得更好:在算法开始时获取最大列表的大小并调用它LARGEST_SIZE- 这个将在每一轮中得到它.现在对于所有其他列表,它们应该仅用于starting_size_of_the_list/LARGEST_SIZE轮次.我希望你知道我的意思.这样您就可以均匀地分隔所有项目.但尽管如此,它仍然不完美!

好的,所以我会尝试更具体.假设您有4个尺寸列表:30 15 6 3

对于第一个列表,您将每30/30轮使用它,这是1,所以每1轮.这意味着每一次.对于第二个列表,您将使用它15/30,即每2轮0.5.第三名:6/30 - >每5回合一次.最后列表:3月30日 - >每10轮.这应该真的给你一个很好的间距的项目.

这当然是一个很好的例子,对于其他数字,它有点丑陋.对于非常少量的物品,这不会得到完美的结果.但是对于大量的物品,它应该工作得很好.

Answer 2

您可以生成一系列有理数,表示每种颜色的间距均匀.然后,对所有这些数字进行排序.

例:

• 5× B:数字是(1/10 3/10 5/10 7/10 9/10)
• 3× R:数字是(1/6 3/6 5/6)
• 排序:((1/10"B")(1/6"R")(3/10"B")(5/10"B")(3/6"R")(7/10"B" )(5/6"R")(9/10"B"))
• => BRBBRBRB

当数字相等时,应用二级排序,这可以是任意的,但应该是一致的.

请注意,各个序列已经排序,因此您可以通过合并进行排序,在这种情况下只是O(n·log m)(n是所有计数的总和,m是颜色数).这可以通过懒惰地生成数字来进一步优化.

最终算法不需要显式排序:

• 将B计数器设置为(/(*2 5))=> 1/10
• 将R计数器设置为(/(*2 3))=> 1/6
• 设置B步骤加倍B计数器
• 设置R步骤加倍R计数器
• 环
  • 使用最低计数器中的一种颜色并将其放入结果中
  • 以步长计数的步骤
  • 直到所有计数器都> = 1

由于你需要n个循环步骤,并且每次必须找到m个最小值,这似乎在O(n·m)上运行.但是,您可以将计数器保持在最小堆中,以使其再次降至O(n·log m).