python - 从列表创建组合而不考虑相邻元素

Question

我想从列表中生成组合，而不考虑相邻元素。

我尝试过一种代码，它提供组合而不考虑相邻元素，并且它适用于列表中的唯一元素。但它不适用于列表中的重复元素，例如。 [4,5,4,3]

代码:

import itertools

b = []    
stuff = [4,5,4,3]

for L in range(2, len(stuff)+1):

    for subset in itertools.combinations(stuff, L):
        a =list(subset)       

        for i in range(1,len(a)):  

            if stuff.index(a[i-1]) == stuff.index(a[i])-1:

                a.clear()

                break

            else:

                b.append(a)

print('b = ',b)   

预期结果 = [[4,4],[4,3],[5,3]]

实际结果 = [[4, 4], [4, 3], [5, 4], [5, 3], [4, 3], [4, 4, 3], [4 , 4, 3], [5, 4, 3], [5, 4, 3]]

我可以用例子来解释:假设列表是[1,2,3,4,5]，那么可能的非相邻组合是[[1,3],[1,4],[1,5]， [2,4]、[2,5]、[3,5]、[1,3,5]]。我想要这些组合。我正在尝试的代码与唯一集配合得很好，但是当给定列表中的数字重复时，例如 [1,3,2,3,2,5]，那么在获取索引时，它总是获取前 3 个而不是其他一。那么如何从这个集合中获得组合

Answer 1

不要生成所有的itertools.combinations，然后用index过滤掉有效的组合，这样(a)效率非常低，(b)不适用于重复元素，您应该实现自己的组合算法，这一点也不难，可能看起来像这样:

def comb(lst, num):
    if num == 0:
        yield []
    if 0 < num <= len(lst):
        first, *rest = lst
        for c in comb(rest, num-1):
            yield [first] + c
        for c in comb(rest, num):
            yield c

要添加“无相邻元素”约束，只需跟踪是否获取了最后一个元素，如果不是，则仅添加下一个元素:

def comb_no_adj(lst, num, last=False):
    if num == 0:
        yield []
    if 0 < num <= len(lst):
        first, *rest = lst
        if not last:
            for c in comb_no_adj(rest, num-1, True):
                yield [first] + c
        for c in comb_no_adj(rest, num, False):
            yield c

comb_no_adj([1,2,3,4,5,6], 3) 的示例组合为 [1, 3, 5], [1, 3, 6] , [1, 4, 6], [2, 4, 6] (此示例不包含重复项，只是为了更容易理解；因为该算法不包含重复项使用 index，重复元素不是问题。)

<小时/>

更新:事实上，先生成所有组合，然后过滤无效组合是行不通的。考虑以下示例:[1,1,1]。包含两个元素的所有组合均为 [1,1], [1,1], [1,1] (第一个和第二个、第一个和第三个以及第二个和第三个 1)。您将如何决定保留哪些以及丢弃哪些？ [1,1,1,1] 的情况变得更糟。 (不过，您可以生成元素索引对的所有组合，然后过滤它们，但由于无论如何都会过滤掉大量组合，因此效率仍然较低。)