Better algorithm to riffle shuffle (or interleave) multiple lists of varying lengths

I like to watch my favorite TV shows on the go. I have all episodes of each show I'm following in my playlist. Not all shows consist of the same number of episodes. Unlike some who prefer marathons, I like to interleave episodes of one show with those of another.

For example, if I have a show called ABC with 2 episodes, and a show called XYZ with 4 episodes, I would like my playlist to look like:

XYZe1.mp4
ABCe1.mp4
XYZe2.mp4
XYZe3.mp4
ABCe2.mp4
XYZe4.mp4

One 开发者_高级运维way to generate this interleaved playlist is to represent each show as a list of episodes and perform a riffle shuffle on all shows. One could write a function that would compute, for each episode, its position on a unit-time interval (between 0.0 and 1.0 exclusive, 0.0 being beginning of season, 1.0 being end of season), then sort all episodes according to their position.

I wrote the following simple function in Python 2.7 to perform an in-shuffle:

def riffle_shuffle(piles_list):
    scored_pile = ((((item_position + 0.5) / len(pile), len(piles_list) - pile_position), item) for pile_position, pile in enumerate(piles_list) for item_position, item in enumerate(pile))
    shuffled_pile = [item for score, item in sorted(scored_pile)]
    return shuffled_pile

To get the playlist for the above example, I simply need to call:

riffle_shuffle([['ABCe1.mp4', 'ABCe2.mp4'], ['XYZe1.mp4', 'XYZe2.mp4', 'XYZe3.mp4', 'XYZe4.mp4']])

This works fairly well most of the time. However, there are cases where results are non-optimal--two adjacent entries in the playlist are episodes from the same show. For example:

>>> riffle_shuffle([['ABCe1', 'ABCe2'], ['LMNe1', 'LMNe2', 'LMNe3'], ['XYZe1', 'XYZe2', 'XYZe3', 'XYZe4', 'XYZe5']])
['XYZe1', 'LMNe1', 'ABCe1', 'XYZe2', 'XYZe3', 'LMNe2', 'XYZe4', 'ABCe2', 'LMNe3', 'XYZe5']

Notice that there are two episodes of 'XYZ' that appear side-by-side. This situation can be fixed trivially (manually swap 'ABCe1' with 'XYZe2').

I am curious to know if there are better ways to interleave, or perform riffle shuffle, on multiple lists of varying lengths. I would like to know if you have solutions that are simpler, more efficient, or just plain elegant.

---

Solution proposed by belisarius (thanks!):

import itertools
def riffle_shuffle_belisarius(piles_list):
    def grouper(n, iterable, fillvalue=None):
        args = [iter(iterable)] * n
        return itertools.izip_longest(fillvalue=fillvalue, *args)
    if not piles_list:
        return []
    piles_list.sort(key=len, reverse=True)
    width = len(piles_list[0])
    pile_iters_list = [iter(pile) for pile in piles_list]
    pile_sizes_list = [[pile_position] * len(pile) for pile_position, pile in enumerate(piles_list)]
    grouped_rows = grouper(width, itertools.chain.from_iterable(pile_sizes_list))
    grouped_columns = itertools.izip_longest(*grouped_rows)
    shuffled_pile = [pile_iters_list[position].next() for position in itertools.chain.from_iterable(grouped_columns) if position is not None]
    return shuffled_pile

Example run:

>>> riffle_shuffle_belisarius([['ABCe1', 'ABCe2'], ['LMNe1', 'LMNe2', 'LMNe3'], ['XYZe1', 'XYZe2', 'XYZe3', 'XYZe4', 'XYZe5']])
['XYZe1', 'LMNe1', 'XYZe2', 'LMNe2', 'XYZe3', 'LMNe3', 'XYZe4', 'ABCe1', 'XYZe5', 'ABCe2']

---

A deterministic solution (ie not random)

Sort your shows by decreasing number of episodes.

Select the biggest and arrange a matrix with the number of columns corresponding to the number of episodes of this one, filled in the following way:

A   A   A   A   A   A  <- First show consist of 6 episodes
B   B   B   B   C   C  <- Second and third show - 4 episodes each
C   C   D   D          <- Third show 2 episodes

Then collect by columns

{A,B,C}, {A,B,C}, {A,B,D}, {A,B,D}, {A,C}, {A,C} 

Then Join

{A,B,C,A,B,C,A,B,D,A,B,D,A,C,A,C}

And now assign sequential numbers

{A1, B1, C1, A2, B2, C2, A3, B3, D1, A4, B4, D2, A5, C3, A6, C4}

Edit

Your case

[['A'] * 2, ['L'] * 3, ['X'] * 5])

X  X  X  X  X
L  L  L  A  A

-> {X1, L1, X2, L2, X3, L3, X4, A1, X5, A2}

Edit 2

As no Python here, perhaps a Mathematica code may be of some use:

l = {, , ,};                                 (* Prepare input *)
l[[1]] = {a, a, a, a, a, a};
l[[2]] = {b, b, b, b};
l[[3]] = {c, c, c, c};
l[[4]] = {d, d};
le = Length@First@l;

k = DeleteCases[                              (*Make the matrix*)
   Flatten@Transpose@Partition[Flatten[l], le, le, 1, {Null}], Null];

Table[r[i] = 1, {i, k}];                      (*init counters*)
ReplaceAll[#, x_ :> x[r[x]++]] & /@ k         (*assign numbers*)

->{a[1], b[1], c[1], a[2], b[2], c[2], a[3], b[3], d[1], a[4], b[4], 
   d[2], a[5], c[3], a[6], c[4]}

---

My try:

program, play = [['ABCe1.mp4', 'ABCe2.mp4'], 
                 ['XYZe1.mp4', 'XYZe2.mp4', 'XYZe3.mp4', 'XYZe4.mp4', 
                  'XYZe5.mp4', 'XYZe6.mp4', 'XYZe7.mp4'],
                 ['OTHERe1.mp4', 'OTHERe2.mp4']], []
start_part = 3
while any(program):
    m = max(program, key = len)
    if (len(play) >1 and 
        play[-1][:start_part] != m[0][:start_part] and 
        play[-2].startswith(play[-1][:start_part])):
        play.insert(-1, m.pop(0))
    else:
        play.append(m.pop(0))

print play

---

This would ensure that there is at least 1 and no more than 2 other episodes between two successive episodes of a show:

• While there are more than 3 shows, chain two shortest (i.e. having least episodes) shows together end-to-end.
• Let A be the longest show and B and C the other two.
• If B is shorter than A, pad it with None's at the end
• If C is shorter than A, pad it with None's at the beginning
• Shuffled playlist is [x for x in itertools.chain(zip(A,B,C)) if x is not None]

---

This will ensure true shuffle i.e. a different result each time, with no contiguous items as much as possible.

The one you ask probably could return a few (1, 2) results limited by your requests.

from random import choice, randint
from operator import add

def randpop(playlists):
    pl = choice(playlists)
    el = pl.pop(randint(0, len(pl) -1))
    return pl, el

def shuffle(playlists):
    curr_pl = None
    while any(playlists):
        try:
            curr_pl, el = randpop([pl for pl in playlists if pl and pl != curr_pl])
        except IndexError:
            break
        else:
            yield el
    for el in reduce(add, playlists):
        yield el
    raise StopIteration

if __name__ == "__main__":
    sample = [
        'A1 A2 A3 A4'.split(),
        'B1 B2 B3 B4 B5'.split(),
        'X1 X2 X3 X4 X5 X6'.split()
        ]
    for el in shuffle(sample):
        print(el)

Edit:

Given episodes order is mandatory just simplify randpop function:

def randpop(playlists):
    pl = choice(playlists)
    el = pl.pop(0)
    return pl, el