算法重新排列的数组

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所指出的，为了确保结果中元素的均匀分布，您应该选择与队列中剩余元素的数量成比例的不同队列。

Answer 2

• 随机阵列（Fisher yates shuffle）
• 对于每个x，xA对 - 如果x在xA之后，则切换它们。这可以通过在O(n)中为阵列中的所有元素创建map:Element->Index来完成。

总复杂性：O(n)（时间）平均情况
输出被保证是随机均匀地混洗，从Fisher-耶茨的正确性。

伪代码：

array = shuffle(array) 
map = new map 
for each element e in array with index i: 
    map.add(e,i) 
for each element e in the array: 
    if e is "x" (not "xA"): 
     i = map.get(e) 
     j = map.get(xA) 
     if j<i: 
     swap(arr,i,j) 

• 如果有比只有2（X，XA，XB，...）更多的 - 你可以列出所有这些，排序在主回路，在类似的方式。