python - 获取用零填充列表的所有排列

Question

我有一个长度为 n 的列表 ls，并且想要获取长度为 m(其中 m > n)且包含 ls 以相同的顺序，加上 (m - n) 个零，插入到每个可能的位置组合处。

例如:ls = [1, 2, 3] 和 m = 4 应返回

[[1, 2, 3, 0],
 [1, 2, 0, 3],
 [1, 0, 2, 3],
 [0, 1, 2, 3]]

和 ls = [1, 2, 3] 和 m = 5 应该返回

[[1, 2, 3, 0, 0],
 [1, 2, 0, 3, 0],
 [1, 2, 0, 0, 3],
 [1, 0, 2, 3, 0],
 [1, 0, 2, 0, 3],
 [1, 0, 0, 2, 3],
 [0, 1, 2, 3, 0],
 [0, 1, 2, 0, 3],
 [0, 1, 0, 2, 3],
 [0, 0, 1, 2, 3]]

该解决方案应该快速且内存高效 - 特别是，它应该避免生成重复的解决方案。如有任何帮助，我们将不胜感激!

一次有效(但效率低下)的尝试:

ls = [1, 2, 3]
m = 4

from itertools import permutations

n = len(ls)
results = []
for t in set(permutations('1' * n + '0' * (m - n))):
    idxs = [i for i, j in enumerate(t) if j == '1']
    result = [0] * m
    for idx, value in zip(idxs, ls):
        result[idx] = value
    results.append(result)

Answer 1

使用itertools.combinations生成插入零的位置的每个组合。然后使用列表推导式选择 0 或下一个原始元素来构建新列表。

# Pad list orig with zeroes, out to "m" total elements.
from itertools import combinations

orig = [1, 2, 3]
m = 5
n = len(orig)

padded = []

for pad_idx in combinations(range(m), m-n):
    t = orig[:]
    padded.append( [0 if i in pad_idx else t.pop(0)
                    for i in range(m)] )

print(padded)

输出(为了便于阅读而格式化):

[[0, 0, 1, 2, 3], 
 [0, 1, 0, 2, 3], 
 [0, 1, 2, 0, 3], 
 [0, 1, 2, 3, 0], 
 [1, 0, 0, 2, 3], 
 [1, 0, 2, 0, 3], 
 [1, 0, 2, 3, 0], 
 [1, 2, 0, 0, 3], 
 [1, 2, 0, 3, 0], 
 [1, 2, 3, 0, 0]]