Python：如何在仅更改特定元素时查找列表的所有组合

Question

使用python，我试图通过只更改列表中的特定元素来查找列表的所有组合。例如，如果我有一个列表[1,2,3,4,5,6,7,8,9]，并在其中附加了3个字符串，我会：

[1,2,3,4,5,6,7,8,9,'string','string','string']

然后我想找出列表中所有的组合，当只允许改变字符串的位置时。你知道吗

例如

[1,2,3,4,5,'string',6,7,8,9,'string','string']
[1,2,'string',3,4,5,'string',6,7,'string',8,9]
['string',1,'string',2,3,4,'string',5,6,7,8,9]

等等，同时仍然保持原始的数字列表以相同的升序排列。 我不一定要一次存储每一个简单的组合，我只是想：

• 遍历所有可能的组合
• 对于每种可能性，检查一个条件
• 如果为true，则将列表分配给变量
• 如果为false，则继续迭代

我一直在试图找到一个解决方案，而不必使用不合理数量的for循环，这将适用于附加了更多字符串的较大列表。我一直在考虑使用itertools，但似乎找不到一种方法。你知道吗

我发现的一个解决方案可能是只使用itertools.permutations（带有附加字符串的列表），然后使用条件检查数字是否按升序排列，但我担心这种方法会非常低效并占用大量内存，尤其是在处理较大的列表时。你知道吗

如有任何帮助，我们将不胜感激。你知道吗

Answer 1

可以对生成器使用递归：

data, s = [1,2,3,4,5,6,7,8,9], ['foo', 'bar', 'foobar']
def groups(d):
   if all(i in d for i in s):
     yield d
   else:
     for i in range(len(d)):
       for k in filter(lambda x:x not in d, s):
          yield from groups(d[:i]+[k]+d[i:])

result = [*set(map(tuple, groups(data)))]

输出：

[(1, 2, 3, 4, 'foo', 'foobar', 5, 'bar', 6, 7, 8, 9), 
 (1, 'foo', 'foobar', 2, 'bar', 3, 4, 5, 6, 7, 8, 9), 
 (1, 'foobar', 2, 3, 'bar', 4, 5, 6, 'foo', 7, 8, 9), 
 ('bar', 'foo', 1, 2, 'foobar', 3, 4, 5, 6, 7, 8, 9), 
 (1, 2, 'foobar', 3, 4, 5, 6, 'bar', 'foo', 7, 8, 9), 
 (1, 2, 3, 'foo', 'foobar', 4, 5, 6, 'bar', 7, 8, 9), 
 (1, 'bar', 2, 3, 'foo', 4, 5, 6, 7, 'foobar', 8, 9), 
 (1, 2, 3, 'foobar', 4, 5, 'bar', 6, 7, 'foo', 8, 9), 
 (1, 2, 3, 'foo', 4, 5, 6, 'foobar', 'bar', 7, 8, 9), 
 (1, 'foobar', 2, 3, 4, 'bar', 5, 'foo', 6, 7, 8, 9)
 ...
 ]

Answer 2

我想你可以在@wjandrea的评论里做点什么：

from itertools import combinations, permutations

lst = [1,2,3,4,5,6,7,8,9]

strings = ['foo', 'bar', 'foobar']

for positions in combinations(range(len(lst) + len(strings)), len(strings)):
    for permutation in permutations(strings, len(strings)):
        cop = lst[:]
        for string, pos in zip(permutation, positions):
            cop.insert(pos, string)
        print(cop)

输出（小样本）

['foo', 'foobar', 1, 2, 3, 'bar', 4, 5, 6, 7, 8, 9]
['bar', 'foo', 1, 2, 3, 'foobar', 4, 5, 6, 7, 8, 9]
['bar', 'foobar', 1, 2, 3, 'foo', 4, 5, 6, 7, 8, 9]
['foobar', 'foo', 1, 2, 3, 'bar', 4, 5, 6, 7, 8, 9]
['foobar', 'bar', 1, 2, 3, 'foo', 4, 5, 6, 7, 8, 9]
['foo', 'bar', 1, 2, 3, 4, 'foobar', 5, 6, 7, 8, 9]
['foo', 'foobar', 1, 2, 3, 4, 'bar', 5, 6, 7, 8, 9]

请注意，此解决方案假设您可以对字符串重新排序。你知道吗

Answer 3

@DanielMesejo的答案是有效的，但是使用list.insert方法将每个字符串插入到数字列表副本中的位置，这是低效的，因为list.insert每次迭代的平均时间复杂度是O（n）。你知道吗

根据位置的组合和字符串的排列构造每个列表的一种更有效的方法是使用dict将位置映射到字符串，然后在整个长度上迭代位置，如果位置在所述dict中，则在该位置输出字符串；否则，使用迭代器。你知道吗

为了获得更高的效率，您可以在combinations和permutation的两个生成器上使用itertools.product，以避免使用嵌套循环反复计算相同的排列：

from itertools import combinations, permutations, product

lst = [1,2,3,4,5,6,7,8,9]
strings = ['foo', 'bar', 'foobar']

total_len = len(lst) + len(strings)
for positions, permutation in product(combinations(range(total_len), len(strings)),
                                      permutations(strings, len(strings))):
    string_pos = dict(zip(positions, permutation))
    numbers = iter(lst)
    print([string_pos[i] if i in string_pos else next(numbers) for i in range(total_len)])