如何检查某个相邻子阵的和是否等于N？

Question

假设我有一个这样的序列列表。你知道吗

我想删除所有序列，其中它的总和=N和/或它有一个连续的子数组和=N

例如，如果N=4，则（1,1,2）无效，因为其总数为4。（1,1,3）也无效，因为（1,3）也是4。（1,3,1）也因同样的原因无效。你知道吗

lst = [ 
    (1,1,1), (1,1,2), (1,1,3), 
    (1,2,1), (1,2,2), (1,2,3), 
    (1,3,1), (1,3,2), (1,3,3), 
    (2,1,1), (2,1,2), (2,1,3), 
    (2,2,1), (2,2,2), (2,2,3), 
    (2,3,1), (2,3,2), (2,3,3), 
    (3,1,1), (3,1,2), (3,1,3), 
    (3,2,1), (3,2,2), (3,2,3), 
    (3,3,1), (3,3,2), (3,3,3) 
] 

有什么方法可以做到这一点？你知道吗

我现在正在试着看我是否能够删除那些总数不一定是N的倍数，但不一定是其相邻子数组的序列，但我没有成功

   for elements in list(product(range(1,n), repeat=n-1)):
        lst.append(elements)
    for val in lst:
        if np.cumsum(val).any() %n != 0:
            lst2.append(val) # append value to a filtered list

Answer 1

您可以将问题分为两个子问题：

1. 列表中的元素总计为N。然后您可以简单地测试：

   if sum(myList) == N:
       # do fancy stuff
   

2. 列表中的元素总和不等于N。在这种情况下，可能有一个子序列总和为N。要找到它，让我们定义两个指针，l和r。它们的名字代表left和right，并将定义子序列的边界。那么，解决方案如下：

   r = 1
   l = 0
   while r <= len(myList):
       sum_ = sum(myList[l:r])
       if sum_ < 4:
           r += 1
       elif sum_ > 4:
           l += 1
       else:
           # do fancy stuff and exit from the loop
           break
   

   它的工作原理如下。首先初始化l和r，以便考虑只由myList的第一个元素组成的子序列。然后，对子序列的元素求和，如果和小于N，则通过将1添加到r来放大子序列。如果大于N，则通过将1添加到l来限制子序列。

---

感谢eozd：

上述算法仅在列表元素为非负时有效。你知道吗

Answer 2

可以使用itertools.combinations生成片索引的所有组合，以测试子序列的和：

from itertools import combinations
[t for t in lst if not any(sum(t[l:h+1]) == 4 for l, h in combinations(range(len(t)), 2))]

这将返回：

[(1, 1, 1), (1, 2, 3), (2, 3, 2), (2, 3, 3), (3, 2, 1), (3, 2, 3), (3, 3, 2), (3, 3, 3)]