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

Я думаю, вы могли бы что-то сделать в строке комментариев @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 требует в среднем сложности времени O (n) за итерацию.

Более эффективный способ построить каждый список в соответствии с комбинацией позиций и перестановкой строк - это использовать dict, который отображает позиции в строки, а затем повторяет позицию по всей длине,и если позиция находится в указанном dict, выведите строку в этой позиции;в противном случае выведите следующее число в списке с помощью итератора.

Для еще большей эффективности вы можете использовать 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

Вы можете сделать это с возвратом. На каждом этапе пути мы либо добавляем число, либо строку (поэтому путь - это серия решений). Если мы достигаем конца пути, мы добавляем копию этого пути к результату.

Мы можем применить этот подход ко всем перестановкам списка 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! перестановок списка строк, и для каждого мы возвращаемся. Длина каждого пути составляет (n + s) , и мы делаем 2 операции за шаг и копию в конце.

Answer 4

Вы можете использовать рекурсию с генератором:

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