给定一个 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'总是出现在[=15=之后]，'T'总是出现在[=14=之后]，'O'总是出现在[=19=之后],等等...

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

请注意：

我想要一个适用于任何给定列表列表的通用代码，而不仅仅是“dog cat fish”；
有没有复制人并不重要，因为每个项目都是可区分的。

谁能为此推荐一个快速 Python 算法？

Answer 1

尝试：

from itertools import permutations, chain

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

x = [[(i1, i2, o) for i2, o in enumerate(subl)] for i1, subl in enumerate(ll)]
l = sum(len(subl) for subl in ll)


def is_valid(c):
    seen = {}
    for i1, i2, _ in c:
        if i2 != seen.get(i1, -1) + 1:
            return False
        else:
            seen[i1] = i2
    return True


for c in permutations(chain(*x), l):
    if is_valid(c):
        print([o for *_, o in c])

打印：

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

...

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

Answer 2

为简单起见，让我们从列表中的两个列表项开始。

from itertools import permutations

Ls = [['D', 'O', 'G'], ['C', 'A', 'T']]
L_flattened = []
for L in Ls:
    for item in L:
        L_flattened.append(item)

print("L_flattened:", L_flattened)

print(list(permutations(L_flattened, len(L_flattened))))


[('D', 'O', 'G', 'C', 'A', 'T'), ('D', 'O', 'G', 'C', 'T', 'A'), ('D', 'O', 'G', 'A', 'C', 'T'), ('D', 'O', 'G', 'A', 'T', 'C'), ('D', 'O', 'G', 'T', 'C', 'A'), ('D', 'O', 'G', 'T', 'A', 'C'), ('D', 'O', 'C', 'G', 'A', 'T'), 
 ('D', 'O', 'C', 'G', 'T', 'A'), ('D', 'O', 'C', 'A', 'G', 'T'), ('D', 'O', 'C', 'A', 'T', 'G'),
 ...

请注意排列的大小非常增长。在您的示例中，有 10 个项目和 Permutation(10, 10) = 3628800.

我建议你计算排列 here 以便在运行实际代码之前获得一个想法（这可能会导致系统内存 error/freeze/crash）。

Answer 3

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

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

Answer 4

您可以尝试验证所有可能的排列：

import random
import itertools
import numpy as np

ll = [['D', 'O', 'G'], ['C', 'A', 'T'], ['F', 'I', 'S', 'H']]
flat = [x for l in ll for x in l]

all_permutations = list(itertools.permutations(flat))
good_permutations = []
count = 0
for perm in all_permutations:
  count += 1
  cond = True
  for l in ll:
    idxs = [perm.index(x) for i, x in enumerate(flat) if x in l]
    # check if ordered
    if not np.all(np.diff(np.array(idxs)) >= 0):
      cond = False
      break
  if cond == True:
    good_permutations.append(perm)
  if count >= 10000:
    break

print(len(good_permutations))

这只是一个基本的解决方案，因为它的计算速度非常慢（我设置了计数来限制验证的排列数）。

Answer 5

另一种解决方案，但此解决方案不使用任何库。

def recurse(lst, indices, total, curr):
    done = True
    for l, (pos, index) in zip(lst, enumerate(indices)):
        if index < len(l): # can increment index
            curr.append(l[index]) # add on corresponding value
            indices[pos] += 1 # increment index
            recurse(lst, indices, total, curr)
            # backtrack
            indices[pos] -= 1
            curr.pop()
            done = False # modification made, so not done

    if done: # no changes made
        total.append(curr.copy())

    return

def list_to_all_flat(lst):
    seq = [0] * len(lst) # set up indexes
    total, curr = [], []
    recurse(lst, seq, total, curr)
    return total

if __name__ == "__main__":
    lst = [['D', 'O', 'G'], ['C', 'A', 'T'], ['F', 'I', 'S', 'H']]
    print(list_to_all_flat(lst))

Answer 6

您可以使用递归生成器函数：

ll = [['D', 'O', 'G'], ['C', 'A', 'T'], ['F', 'I', 'S', 'H']]
def get_combos(d, c = []):
   if not any(d) and len(c) == sum(map(len, ll)):
       yield c
   elif any(d):
      for a, b in enumerate(d):
         for j, k in enumerate(b):
            yield from get_combos(d[:a]+[b[j+1:]]+d[a+1:], c+[k])

print(list(get_combos(ll)))

输出（前十个排列）：

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

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

Given a Python list of lists, find all possible flat lists that keeps the order of each sublist?

python

algorithm

list

permutation

python-3.x