Python: How to find all combinations of a list when changing only specific elements

user_11907503 0
Viewed 727

Using python I am trying to find all combinations of a list by changing only specific elements in it. For example, if I have a list [1,2,3,4,5,6,7,8,9] and append 3 strings to it, I would have: 

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

I would then like to find all combinations the list can take when only the position of the strings are allowed to change.

e.g

[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, whilst still keeping the original list of numbers in the same ascending order. I am not necessarily trying to store every simple combination at once, I am just trying something like:

  • Iterate through all of the possible combinations
  • For each possibility, check a condition
  • If true, then assign the list to a variable
  • If false, then continue iterating

I have been trying to find a solution without having to use an unreasonable amount of for loops and which would be applicable to larger lists with possibly more strings appended. I have been looking at using itertools but can't seem to find an approach.

A solution I found could be to just use itertools.permutations (list with appended strings), and then use conditions to check if the numbers are in ascending order, but I was worried this approach would be really inefficient and take up heaps of memory, especially when working with larger lists.

Any help would be appreciated, thanks in advance.

itertools recursion list python loops
4 Answers

I guess you could do something in the line of the comments by @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)

Output (small sample)

['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]

Note that this solution assumes that you can reorder the strings.

user_40015920

@DanielMesejo's answer works but uses the list.insert method to insert each string into its position in a copy of the number list, which is inefficient since list.insert takes an average time complexity of O(n) per iteration.

A more efficient way to construct each list according to the combination of positions and permutation of strings is to use a dict that maps positions to the strings, then iterate the position over the total length, and if the position is in the said dict, output the string at that position; otherwise output the next number in the list by using an iterator.

For even better efficiency, you can use itertools.product over the two generators of combinations and permutation to avoid having to use a nested loop that repeatedly computes the same permutations over and over again:

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

You can use recursion with a generator:

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

Output:

[(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)
 ...
 ]
user_73267380

You can do this with backtracking. At each step in a path, we either append a number or a string (a path, therefore, is a series of decisions). If we reach the end of a path, we append a copy of that path to the result.

We can apply this approach to all permutations of a the strings list to get our final answer:

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

The time complexity of this approach is O(s! (n + s) 2 (n + s)). This is because there are s! permutations of the string list, and for each we backtrack. The length of each path is (n + s) and we make 2 operations per step and a copy at the end.

user_18226980
Related