Finding all possible combinations of elements in a list of integers. all elements of any of the new-CodePudding

I need a function that gets a list as an input and returns all the combinations with the maximum amount of integers used (here 5) which don't have 2 adjacent integers like 2, 3 or 6,7.

list0 = [0, 3, 4, 6, 10, 11, 12, 13]

all_combinations = magic_function(list0)

all_combinations would be this:

[[0, 3, 6, 10, 12],
 [0, 3, 6, 11, 13],
 [0, 4, 6, 10, 12],
 [0, 4, 6, 11, 13]]

It could be done by getting all combinations and then picking out the correct ones, but I can't have it use much memory or be slow, because it has to work with lists with length up to 98 elements.

CodePudding user response：

My approach is as follows:

import itertools

lst = [0, 3, 4, 6, 10, 11, 12, 13] # 0 | 3 4 | 6 | 10 11 12 13

chunks, chunk = [], [] # defining chunk here is actually useless
prev = None
for x in lst:
    if prev is None or x - prev > 1: # if jump > 1
        chunks.append(chunk := []) # insert a brand-new chunk
    chunk.append(x)
    prev = x # update the previous number

def max_nonadjacents(chunk): # maximal nonadjacent sublists (given a chunk)
    if not chunk or len(chunk) % 2: # odd length is easy
        return {tuple(chunk[::2])}
    return{tuple((chunk[:i]   chunk[i 1:])[::2]) for i in range(len(chunk))}

output = [list(itertools.chain.from_iterable(prod)) # flattening
              for prod in itertools.product(*map(max_nonadjacents, chunks))]

print(output)
# [[0, 3, 6, 11, 13], [0, 3, 6, 10, 12], [0, 3, 6, 10, 13], [0, 4, 6, 11, 13], [0, 4, 6, 10, 12], [0, 4, 6, 10, 13]]

I am assuming that the input list is sorted.

Basically, my approach starts with recognizing that the problem can be divided into smaller pieces; the list can be divided into chunks, where each chunk comprises of running integers; [0], [3, 4], [6], [10, 11, 12, 13].

Then you can see you can get all the possible combinations by taking all the maximal non-adjacent lists from each chunk, and then taking the products of the lists across the chunks.

The code follows this procedure: (i) get the chunks, (ii) define a helper function max_nonadjacents that extracts all the maximal non-adjacent lists, (iii) apply it to each chunk (map(max_nonadjacents, ...)), and then (iv) take the products.

CodePudding user response：

You can use a recursive generator function:

def combos(d, c = []):
   if len(c) == 5:
      yield c
   else:
      for i in d:
         if not c or c[-1] 1 < i:
            yield from combos(d, c [i])

list0 = [0, 3, 4, 6, 10, 11, 12, 13]
print(list(combos(list0)))

Output:

[[0, 3, 6, 10, 12], 
 [0, 3, 6, 10, 13], 
 [0, 3, 6, 11, 13], 
 [0, 4, 6, 10, 12], 
 [0, 4, 6, 10, 13], 
 [0, 4, 6, 11, 13]]