Лучший алгоритм для перемешивания (или чередования) нескольких списков разной длины

Я люблю смотреть свои любимые телешоу на ходу. В моем плейлисте есть все эпизоды каждого шоу, за которым я смотрю. Не все шоу состоят из одинакового количества серий. В отличие от некоторых, кто предпочитает марафоны, мне нравится чередовать эпизоды одного шоу с эпизодами другого.

Например, если у меня есть шоу под названием ABC с 2 эпизодами и шоу под названием XYZ с 4 эпизодами, я бы хотел, чтобы мой плейлист выглядел так:

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

Один из способов создать этот чередующийся плейлист - представить каждое шоу в виде списка эпизодов и выполнять тасование на всех шоу. Можно написать функцию, которая будет вычислять для каждого эпизода его позицию в единичном временном интервале (от 0,0 до 1,0 исключая, 0,0 - начало сезона, 1,0 - конец сезона), а затем сортировать все эпизоды в соответствии с их положением.

Я написал следующую простую функцию в Python 2.7 для выполнения в случайном порядке:

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

Чтобы получить список воспроизведения для вышеприведенного примера, мне просто нужно вызвать:

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

В большинстве случаев это работает довольно хорошо. Однако бывают случаи, когда результаты неоптимальны - две соседние записи в плейлисте - это эпизоды одного шоу. Например:

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

Обратите внимание, что есть два эпизода «XYZ», которые появляются рядом. Эту ситуацию можно легко исправить (вручную поменять местами «ABCe1» на «XYZe2»).

Мне любопытно узнать, есть ли лучшие способы чередования или перетасовки нескольких списков разной длины. Я хотел бы знать, есть ли у вас решения, которые проще, эффективнее или просто элегантно.

Решение, предложенное belisarius (спасибо!):

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

Пример выполнения:

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