Mix two lists python
You could implement a greedy algorithm which tries to yield the most common item as frequently as possible (i.e. up to twice), and then yield the next most common item when necessary.
This has two advantages over search by random shuffle:
The greedy algorithm is much faster as the length of
items
increases:In [223]: %timeit list(intermix([1]*10+[2]*5)) 10000 loops, best of 3: 39.8 µs per loop In [222]: %timeit intermix_random([1]*10+[2]*5) 100 loops, best of 3: 6.85 ms per loop
It can identify when there is no solution, whereas a random shuffle search loops forever if visited shuffles are not cached.
import collections
def intermix(items, nconsecutive=2):
counter = collections.Counter(items)
# sort from most common to least common
items = sorted(items, key=counter.get, reverse=True)
N = len(items)
count = 0
# remember the last two values
last = []
for i in range(N):
val = items[i]
if len(last) < nconsecutive:
if last and val == last[-1]:
last.append(val)
else:
last = [val]
counter[val] -= 1
yield val
else:
# last is full; find a different value
for j in range(i, N):
if items[j] != last[-1]:
items[i], items[j] = items[j], items[i]
val = items[i]
last = [val]
counter[val] -= 1
# as items are yielded, the meaning of "most common" can change.
items[i+1:] = sorted(items[i+1:], key=counter.get, reverse=True)
yield val
break
else:
raise ValueError('No solution possible')
In [184]: list(intermix([1,1,1,1,1,2,2,2,2,2]))
Out[184]: [1, 1, 2, 2, 1, 2, 2, 1, 2, 1]
In [185]: list(intermix([1,0,1,1,2,1,0,1,1,1,2]))
Out[185]: [1, 1, 0, 1, 1, 2, 1, 1, 2, 1, 0]
In [186]: list(intermix([1,0,1,1,2,1,0,1,1,1,1,1,1,2]))
Out[186]: [1, 1, 0, 1, 1, 2, 1, 1, 2, 1, 1, 0, 1, 1]
In [187]: list(intermix([1,0,1,1,2,1,0,1,1,1,1,1,1,1,2]))
ValueError: No solution possible
In [188]: list(intermix([1,0,1,1,2,1,0,1,1,1,1,1,1,1,2], nconsecutive=3))
Out[188]: [1, 1, 1, 0, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 0]