Cfrgtkky

So say I have a list sequences such as this.

I want to remove all sequences where its total sum = N and/or it has a contiguous subarray with sum = N.

For example, if N = 4, then (1,1,2) is not valid since its total is 4. (1,1,3) is also not valid since the (1,3) is also 4. (1,3,1) is also not valid for the same reason.

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) 

] 

What are some ways to do this?

I'm currently trying to see if I'm able to remove sequences whose total is not necessarily a multiple of N but not its contiguous subarrays, but I'm unsuccessful

   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

You can use itertools.combinations to generate all combinations of slice indices to test for sums of subsequences:

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

This returns:

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

You can split your problem into two subproblems:

1. 
   

   The elements in your list sum up to N. Then you can simply test:

   
   
   

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

   
   


2. 
   

   The elements in your list do not sum up to N. In this case, there might be a subsequence that sum up to N. To find it, let's define two pointers, l and r. Their name stand for left and right and will define the boundaries of your subsequence. Then, the solution is the following:

   
   
   

   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
   
   

   
   
   

   It works as follows. First you initialize l and r so that you consider the subsequence consisting of only the first element of myList. Then, you sum the element of the subsequence and if the sum is lower than N, you enlarge the subsequence by adding 1 to r. If it is greater than N, then you restrict the subsequence by adding 1 to l.

   
   

Note thanks to eozd:

The above algorithm works only if the elemnent of the list are non-negative.