How to randomize the order of elements of a list while making sure no consecutive values are equal?

Question

I have a python list of strings, let's say:

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

I want to create a new list whose elements are each element of elems repeated a fixed number of times (let's say twice), in a random order, but while making sure that two consecutive elements never have the same value.

For example, ["D", "B", "A", "B", "D", "C", "A", "C"] is a good result. ["D", "B", "A", "B", "D", "C", "C", "A"] is not (C is repeated in 6th and 7th position).

The simplest idea is probbaly just:

ans = 2*elems
random.shuffle(ans)

and then some code to take care of the repetitions, but all the solutions I can think of involve potentially infinite loops. Is there a simple and reliable way to do that ?

Thanks.

Answer 1

I am assuming that the input list has distinct elements.

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"])

Some output:

['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']