给定一个 Python 列表列表，找到所有可能的保持每个子列表顺序的平面列表？

Question

我有一个列表列表。我想找到所有保持每个子列表顺序的平面列表。举个例子，假设我有一个这样的列表：

ll = [['D', 'O', 'G'], ['C', 'A', 'T'], ['F', 'I', 'S', 'H']]

获得一个解决方案是微不足道的。我设法编写了以下代码，它可以生成一个随机的平面列表，该列表保持每个子列表的顺序。

import random

# Flatten the list of lists
flat = [x for l in ll for x in l]
# Shuffle to gain randomness
random.shuffle(flat)

for l in ll:
    # Find the idxs in the flat list that belongs to the sublist
    idxs = [i for i, x in enumerate(flat) if x in l]
    # Change the order to match the order in the sublist
    for j, idx in enumerate(idxs):
        flat[idx] = l[j]

print(flat)

这可以生成如下所示的平面列表：

['F', 'D', 'O', 'C', 'A', 'G', 'I', 'S', 'T', 'H']
['C', 'D', 'F', 'O', 'G', 'I', 'S', 'A', 'T', 'H']
['C', 'D', 'O', 'G', 'F', 'I', 'S', 'A', 'T', 'H']
['F', 'C', 'D', 'I', 'S', 'A', 'H', 'O', 'T', 'G']

如您所见，'A'总是出现在 之后'C'，'T'总是出现在 之后'A'，'O'总是出现在 之后'D'，等等......

但是，我想获得所有可能的解决方案。

请注意：

1. 我想要一个适用于任何给定列表列表的通用代码，而不仅仅是“狗猫鱼”；
2. 是否有复制品并不重要，因为每个项目都是可区分的。

任何人都可以为此建议一个快速的 Python 算法吗？

Answer 1

假设您要手动组合列表。您可以选择一个列表并获取其第一个元素，然后再次选择一个列表并获取其第一个（未使用的）元素，等等，而不是打乱顺序并将内容放回原处。因此，您需要的算法是这样的：从具有这些特定大小的列表集合中进行选择的所有不同方法是什么？

在您的示例中，您有长度为 3, 3, 4 的列表；假设你有一个桶，里面有三个红球、三个黄球和四个绿球，可能有哪些顺序？对此进行建模，然后只需从相应列表中选择第一个未使用的元素即可获得输出。

说什么？对于您的示例，（不同的）挑选订单将由以下给出

set(itertools.permutations("RRRYYYGGGG"))

对于任何列表列表，我们将使用整数键而不是字母。挑选顺序为：

elements = []
for key, lst in enumerate(ll):
    elements.extend( [ key ] * len(lst))
pick_orders = set(itertools.permutations(elements))

然后，您只需使用每个选择顺序来呈现列表列表中的元素，例如pop(0)（来自列表的副本，因为pop()具有破坏性）。