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

Question

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

Например, если у меня есть шоу под названием 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').

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

---

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

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

Answer 1

Детерминированное решение (т. Е. Не случайное)

Сортировка шоу по уменьшению количества эпизодов.

Выберите самое большое и расположите матрицу с количеством столбцов, соответствующих количеству эпизодов этого, заполненных следующим образом:

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

Затем соберите по столбцам

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

Затем присоединитесь

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

А теперь присвойте порядковые номера

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

Изменить

Ваш случай

[['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}

Редактировать 2

Поскольку здесь нет Python, возможно, код Mathematica может быть полезным:

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

Answer 2

Моя попытка:

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

Answer 3

Это обеспечит наличие не менее 1 и не более 2 других эпизодов между двумя последовательными эпизодами шоу:

• Хотя существует более 3 шоу, цепочка два самая короткая (т.е.наименьшее количество эпизодов) показывают вместе сквозное.
• Пусть A - самое длинное шоу, а B и C - два других.
• Если B короче, чем A, добавьте его Noneв конце
• Если C короче, чем A, заполните его None в начале
• Перемешанный список воспроизведения равен [x for x in itertools.chain(zip(A,B,C)) if x is not None]

Answer 4

Это обеспечит истинное перемешивание, т. Е. Каждый раз новый результат, без максимально возможного количества смежных элементов.

Тот, который вы спросите, может вернуть несколько (1, 2) результатов, ограниченных вашими запросами.

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)

Редактировать:

Данный порядок эпизодов обязателен, просто упростите randpop Функция:

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