Python中的特定混洗列表

Question

所以,我有一个小组列表

[['a', 'b'], ['c', 'd', 'e'], ['f']]

我需要洗牌这个列表的扁平版本

[a, b, c, d, e, f]

以便同一组的元素在彼此相距一定距离处结束.E. g.

[a, c, b, d, f, e]而不是[a, c, b, d, e, f]因为d并且e属于同一组.

我不在乎,如果距离只有一个元素或以上,但任何元素一定不能靠近从中小组的另一个元素.这有什么算法吗？

该算法还需要判断是否无法完成此操作.

Answer 1

此代码生成原始组列表的副本,并且每次从(每个时刻)最大剩余组中获取随机元素.不完全随机化,但是当没有超过一半所有元素的组时,它应该适用于任何情况.

import random

list_of_groups = [['a', 'b'], ['c', 'd', 'e'], ['f']]
l = [group[:] for group in list_of_groups] # make a copy
random.shuffle(l)
out = []
prev_i = -1
while any(a for a in l):
    new_i = max(((i,a) for i,a in enumerate(l) if i != prev_i), key=lambda x: len(x[1]))[0]
    out.append(l[new_i].pop(random.randint(0, len(l[new_i]) - 1)))
    prev_i = new_i

print out