如何随机打乱两个同长度含重复值的数组，使相邻元素（上下左右）不重复？

问题说明 #

现有两个元素数量一致、包含重复值的数组：

first = [1,1,2,2,3,3]
second = [1,1,2,2,3,3]

需要对两个数组进行随机打乱，同时满足以下规则：

1. 每个数组内部，任意元素与其左右相邻元素不重复；
2. 两个数组对应位置的元素不重复。
   合规示例：

first =  [1,2,1,3,2,3]
second = [2,1,3,1,3,2]

实现思路 #

• 先保证单数组内部无相邻重复
  先对其中一个数组（比如first）做随机打乱，之后检查相邻元素是否重复。如果出现相邻重复，就找后面第一个不同的元素交换位置；或者直接用贪心策略构建：从剩余元素里选一个和前一个元素不同的，依次填充，直到所有元素用完，先确保first内部符合相邻不重复的要求。

• 基于第一个数组生成合规的第二个数组
  先统计second初始的元素计数（比如{1:2, 2:2, 3:2}），然后逐个位置生成second的元素：

  • 第0位：选一个和first[0]不同、且计数大于0的元素，放入后对应计数减1；
  • 第i>0位：排除first[i]和second[i-1]这两个值，从剩下的可用元素里选一个计数大于0的，放入后计数减1；
  • 若遇到无可选元素的情况（比如剩余元素刚好是被排除的两个），微调前一个位置的元素——比如把前一个位置的元素和当前候选元素交换，只要不破坏之前的规则，就能继续完成填充。

• 加入随机化保证结果多样性
  第一步打乱first时用随机打乱算法，第二步选择可用元素时，从符合条件的候选里随机挑一个，而非固定选择，这样每次生成的结果都是随机且合规的。

• 全量验证兜底
  生成完两个数组后，遍历所有位置做校验：

  1. 所有位置i，first[i] != second[i]；
  2. 所有位置i>0，first[i] != first[i-1]且second[i] != second[i-1]。
     若有不满足的情况，重新生成或局部调整，直到完全符合规则。

内容的提问来源于stack exchange，提问作者Jimmy