python - 更好的算法来随机播放(或交错)多个不同长度的列表

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 中编写了以下简单函数来执行 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

要获取上述示例的播放列表，我只需调用:

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

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