[ Specific shuffling list in Python ]

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

Answer 3

---

Just a fast, not-very-elegant code:

example = [[1, 2], [3, 4, 5], [6]]
result = []
block = None
last_block = None

while example:
    if block:
        last_block = block

    block = choice(example)

    if last_block:
        example.append(last_block)

    element = choice(block)
    result.append(element)

    block.remove(element)
    example.remove(block)
    example = [a for a in example if a]

print result

Although the problem which might happen is the case when there is only one block for choices. Like in this case:

[1, 6, 2, 3, 4, 5]

Of course there must be some sort of catching this exception, but for now I hope this code can give you some idea how to solve your problem.

• Edited due to an exception happening once in a while.
• Forgot not to use words like "list" as a variable name. Thanks for comment - not it's corrected

Answer 4

---

I'm going to give the "dumb", straightforward answer: just flatten the list, then repeatedly randomly shuffle it until you get an acceptable list.

This method has the property of being uniformly distributed amongst all legal lists, as well as being easy to prove correct and straightforward to code. It's only disadvantage is that it might turn out to be slow -- but given the use case mentioned in another comment, I believe it would be fast enough.

As for "is it possible" -- giving it a first glance, I think it should be possible if and only if no group has more than half of the elements, rounded up. If you consider the first and last elements adjacent, change "rounded up" to "rounded down".