如何随机化列表元素顺序并确保没有连续相同值？

Question

我有一个包含字符串的Python列表，比如说：

elems = ["A", "B", "C", "D"]

我想创建一个新的列表，这个列表里的每个元素都是原列表中每个元素重复固定次数（比如说两次），而且顺序是随机的，但要确保两个相邻的元素不能是相同的。

举个例子，["D", "B", "A", "B", "D", "C", "A", "C"] 这是一个好的结果。["D", "B", "A", "B", "D", "C", "C", "A"] 就不行（因为C在第六和第七个位置重复了）。

最简单的想法可能就是：

ans = 2*elems
random.shuffle(ans)

然后再加一些代码来处理重复的问题，但我想到的所有解决方案都有可能出现无限循环。有没有简单可靠的方法可以做到这一点呢？

谢谢。

Answer 1

我觉得这样做是可行的，虽然看起来不是特别优雅。

import random

elems = ['a','b','c','d']
length = len(elems)

l = []

for i in range(2):
    random.shuffle(elems)
    l.extend( elems )
    if i > 0 and l[ i*length ] == l[ i*length - 1 ]:
        l[i*length-2], l[i*length-1] = l[i*length-1], l[i*length-2]

print l 

Answer 2

我觉得这可以是一个实现你想要的功能的算法：

让我们用 R 来表示你的结果列表。

1. 从 elems 中随机选一个元素 e，然后把 e 加到 R 里。
2. 接下来，把 e 从 elems 中去掉，变成 elems_1 = elems \ e。
3. 再从 elems_1 中随机选一个元素 e_1，然后把 e_1 加到 R 里。
4. 同样，把 e_1 从 elems 中去掉，变成 elems_1 = elems \ e_1。
5. 重复第3步，直到 R 的长度足够为止。

Answer 3

你可以写一个函数，检查列表 x 中两个相邻的值是否相同：

def compareConsecutive(x):
    for i in x:
        if i == x[x.index(i)+1]:
            return False

然后在一个 while 循环中打乱这个列表，直到 compareConsecutive() 不再返回 False 为止：

while compareConsecutive(ans) == False:
    random.shuffle(ans)

如果列表很长，这个过程可能会花费一些时间，因为 random.shuffle() 可能会不断生成包含相邻相同值的列表，但最终会成功的 :)

Answer 4

我假设输入的列表里的元素都是不一样的。

import random

def randomize_carefully(elems, n_repeat=2):
    s = set(elems)
    res = []
    for n in range(n_repeat):
        if res:
            # Avoid the last placed element
            lst = list(s.difference({res[-1]}))
            # Shuffle
            random.shuffle(lst)
            lst.append(res[-1])
            # Shuffle once more to avoid obvious repeating patterns in the last position
            lst[1:] = random.sample(lst[1:], len(lst)-1)
        else:
            lst = elems[:]
            random.shuffle(lst)
        res.extend(lst)
    return res

for i in range(10):
    print randomize_carefully(["A", "B", "C", "D"])

一些输出结果：

['B', 'C', 'D', 'A', 'C', 'A', 'D', 'B']
['B', 'D', 'C', 'A', 'C', 'B', 'A', 'D']
['C', 'B', 'D', 'A', 'B', 'C', 'D', 'A']
['B', 'D', 'A', 'C', 'A', 'B', 'D', 'C']
['D', 'C', 'A', 'B', 'C', 'D', 'A', 'B']
['C', 'D', 'A', 'B', 'D', 'C', 'A', 'B']
['D', 'A', 'C', 'B', 'C', 'A', 'B', 'D']
['C', 'D', 'A', 'B', 'C', 'D', 'A', 'B']
['C', 'B', 'A', 'D', 'A', 'B', 'D', 'C']
['B', 'D', 'A', 'C', 'A', 'D', 'C', 'B']