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

[Гость]

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

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

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


Подробнее: https://stackoverflow.com/questions/545 ... arying-len