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]

etc，同时仍将原始数字列表保持在相同的升序中。我不一定要一次存储每个简单的组合，我只是想尝试类似的事情：

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

我一直在尝试找到一种解决方案，而不必使用过多的for循环，并且该解决方案将适用于可能附加了更多字符串的较大列表。我一直在寻找使用itertools的方法，但似乎找不到方法。

我发现的解决方案可能是只使用itertools.permutations（带有附加字符串的列表），然后使用条件检查数字是否按升序排列，但是我担心这种方法的效率很低并且占用了大量的空间。内存，尤其是在使用较大的列表时。

任何帮助，请先感谢。

Answer 1

我想您可以在@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 2

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

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

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

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)])

Answer 3

您可以对生成器使用递归：

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 4

您可以通过回溯来实现。在路径的每个步骤中，我们都可以附加数字或字符串（因此，路径是一系列决策）。如果到达路径的末尾，则将该路径的副本附加到结果中。

我们可以将这种方法应用于strings列表的所有排列以获得最终答案：

from itertools import permutations

def combinations(nums, strings):
    res = []

    def generate(i, j, string_combo, path):
        if i == len(nums) and j == len(strings):  # path ends
            res.append(path[:])
            return
        if i < len(nums):  # choose number
            path.append(nums[i])
            generate(i + 1, j, string_combo, path)
            path.pop()
        if j < len(strings):  # choose string
            path.append(string_combo[j])
            generate(i, j + 1, string_combo, path)
            path.pop()

    for p in permutations(strings):
        generate(0, 0, p, [])
    return res

result = combinations([1, 2, 3, 4, 5, 6, 7, 8, 9], ['A', 'B', 'C'])
print(len(result))  # 1320

此方法的时间复杂度为
O（s！（n + s）2 （n + s））] >>。这是因为字符串列表存在s！排列，并且对于每个排列，我们都会回溯。每个路径的长度为2 （（n + s）]，但我们在每个路径的末尾都进行复制。