在整数列表中查找所有可能的元素组合.任何新列表的所有元素都必须至少相隔2个

Question

我需要一个函数，它可以获得一个列表作为输入，并返回所有使用了最大整数量的组合(这里是5(，这些组合没有2个相邻的整数，如2、3或6,7。

list0 = [0, 3, 4, 6, 10, 11, 12, 13]
all_combinations = magic_function(list0)

所有的组合都是这样的：

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

它可以通过获取所有组合，然后选择正确的组合来完成，但我不能让它占用太多内存或速度慢，因为它必须处理长度高达98个元素的列表。

Answer 1

您可以使用递归生成器函数：

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

输出：

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

Answer 2

我的方法如下：

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

我假设输入列表已排序。

基本上，我的方法从认识到问题可以分为更小的部分开始；该列表可以被划分为块，其中每个块包括运行的整数；[0]、[3, 4]、[6]、[10, 11, 12, 13]。

然后，您可以看到，通过从每个块中获取所有最大的非相邻列表，然后在块之间获取列表的乘积，可以获得所有可能的组合。

代码遵循以下过程：(i(获取chunks，(ii(定义提取所有最大非相邻列表的辅助函数max_nonadjacents，(iii(将其应用于每个块(map(max_nonadjacents, ...)(，然后(iv(获取乘积。