arrays - 重新排列数组的算法

Question

我有一个数组:

1 1A 2 2A 3 3A 4 4A 5 5A

我需要随机重新排列它，条件是:1A必须在1之后，2A必须在2之后...(不一定喜欢1 1A)

重新排列后的预期结果如下:

1 4 2 4A 3 2A 5 1A 5A 3A

帮助我获得最佳算法(速度最快)

Answer 1

你可以这样尝试:

• 将元素分组到不同的队列中，这样所有具有某种“顺序”的元素都在同一个队列中，例如[[1, 1A], [2, 2A, 2B], [3, 3A], ...]
• 随机选择其中一个队列，删除第一个元素并将其添加到结果中
• 重复直到所有队列都为空

如果部分排序更复杂，例如如果某个元素 a必须在 b 之前和 c , 但 b 之间没有偏序和 c你可以对一棵树或类似的东西做同样的事情。

此外，正如@vib 所指出的，为了确保结果中元素的均匀分布，您应该选择不同的队列，概率与该队列中剩余元素的数量成正比。