Specific shuffling list in Python

Question

So, I have a list of groups

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

and I need to shuffle a flattened version of this list

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

so that elements of the same group would end at some distance from each other. E. g.

[a, c, b, d, f, e] and not [a, c, b, d, e, f], because d and e are in the same group.

I don't care if the distance is just one element or more, but any element must not be near another element from it's group. Is there any algorithm for this?

The algorithm also needs to tell if this cannot be done.

Answer 1

This code makes a copy of your original list of groups and takes each time a random element from the (at each moment) largest remaining group. Not quite randomized, but should work for any case when there is no group with over the half of all elements.

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

Answer 2

Let me take an approach different from the current answers

The Basic principle would be to shuffle every list within the list, sort it based on length, zip_longest based on variable arguments which is passed from the list and finally chain the list and then unwrap it. Particular thing to note here how we can pass a list as a variable args to an iterator, which made life easier here :-)

Lets say your list is

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

My Work List (after copying to preserve the original list)

workList=yourList[::]

Shuffling every list within your list

[random.shuffle(x) for x in workList]

Next we sort the List based on length of each list

workList.sort(key=len,reverse=True)

and then finally chaining over the zipped shuffled list

[x for x in itertools.chain(*[x for x in itertools.izip_longest(*workList)]) if x]

And your Final List looks like

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