时间戳

首页 > 解决方案 > 给定一个 Python 列表，找到所有可能的平面列表，这些列表保持每个子列表的顺序？

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

问题描述

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

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 算法吗？

标签： pythonpython-3.xlistalgorithmpermutation

解决方案

假设您正在手动组合列表。您可以选择一个列表并获取其第一个元素，然后再次选择一个列表并获取其第一个（未使用的）元素，依此类推，而不是打乱并重新排列。所以你需要的算法是这样的：从具有这些特定大小的列表集合中选择的所有不同方法是什么？

在您的示例中，您有长度为 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()具有破坏性）。

推荐阅读