For a list of numbers, find all combinations whose cumulative sum stays within bounds

Question

Let's say I have the following list: [A, A, A, A, A, B, B, B] where A=1, B=-1

Finding all combinations of this list is generally easy (8nCr3), but I want to leave out permutations when the cumulative sum reaches certain bound values, say 0 and 4.

The above example is therefore not right, because the cumulative sum is [1, 2, 3, 4, 5, 4, 3, 2].

The permutation [A, A, B, B, A, A, B, A] is also bad, since here the cumulative sum is [1, 2, 1, 0, 1, 2, 1, 2].

My question is: how do I calculate the number of permutations for any finite list of two components?

I would be most happy with a single function that simply plugs in an analytical solution, should it exist, but an iterative/recursive function should be fine too.

EDIT: I don't actually need to know what the permutations look like. Just their number is sufficient.

Answer 1

Here's a recursive solution using dynamic programming (memoization) in order to handle very large lists instantaneously:

from functools import lru_cache

def boundCumSum(A,loBound,hiBound):
    sRange = range(loBound+1,hiBound)
    
    @lru_cache()
    def count(s,nPos,nNeg):
        if nPos==0 and nNeg==0: return int(s == 0)
        if nPos<0 or nNeg<0 or not s in sRange: return 0
        return count(s-1,nPos-1,nNeg)+count(s+1,nPos,nNeg-1)
    
    nPos   = sum(a>0 for a in A)
    nNeg   = sum(a<0 for a in A)
    return count(sum(A),nPos,nNeg)

The way it works is to start from the sum of values (which will always be the last value in the cumulative sum) and work backward through the +1s and -1 that are available. The recursive part only needs to know how many positives and negatives remain and aims to reach zero when they are exhausted without ever going out of the bounds. This allows use of the lru_cache decorator (from functools) to keep previous results in memory and avoid recalculating them. That memoization is the key to obtaining good performance as the recursive process very often has the same pattern of values to compute from.

Example outputs:

boundCumSum([1,1,1,1,1,-1,-1,-1],0,4)
# 8

boundCumSum([1,1,1,1,1,-1,-1,-1],-2,3)
# 21

boundCumSum([1]*15+[-1]*12,0,4)
# 4096

boundCumSum([1]*150+[-1]*120,0,40)
# 1772031749108746260736075351494970301882401049674141497351113308699264759272661

To verify this, a generator function can be used to show the actual solutions and their cumulative sums:

def genCumSum(A,loBound,hiBound,combo=[]):
    if not A: yield combo; return
    for v,i in {v:i for i,v in enumerate(A)}.items():
        if v<=loBound or v >=hiBound: continue
        yield from genCumSum(A[:i]+A[i+1:],loBound-v,hiBound-v,combo+[v])

...

from itertools import accumulate

for i,solution in enumerate(genCumSum([1,1,1,1,1,-1,-1,-1],0,4),1):
    print(i,solution,list(accumulate(solution)))

1 [1, 1, 1, -1, 1, -1, 1, -1] [1, 2, 3, 2, 3, 2, 3, 2]
2 [1, 1, 1, -1, 1, -1, -1, 1] [1, 2, 3, 2, 3, 2, 1, 2]
3 [1, 1, 1, -1, -1, 1, 1, -1] [1, 2, 3, 2, 1, 2, 3, 2]
4 [1, 1, 1, -1, -1, 1, -1, 1] [1, 2, 3, 2, 1, 2, 1, 2]
5 [1, 1, -1, 1, 1, -1, 1, -1] [1, 2, 1, 2, 3, 2, 3, 2]
6 [1, 1, -1, 1, 1, -1, -1, 1] [1, 2, 1, 2, 3, 2, 1, 2]
7 [1, 1, -1, 1, -1, 1, 1, -1] [1, 2, 1, 2, 1, 2, 3, 2]
8 [1, 1, -1, 1, -1, 1, -1, 1] [1, 2, 1, 2, 1, 2, 1, 2]

...

for i,solution in enumerate(genCumSum([1,1,1,1,1,-1,-1,-1],-2,3),1):
    print(i,solution,list(accumulate(solution)))

1 [1, 1, -1, 1, -1, 1, -1, 1] [1, 2, 1, 2, 1, 2, 1, 2]
2 [1, 1, -1, 1, -1, -1, 1, 1] [1, 2, 1, 2, 1, 0, 1, 2]
3 [1, 1, -1, -1, 1, 1, -1, 1] [1, 2, 1, 0, 1, 2, 1, 2]
4 [1, 1, -1, -1, 1, -1, 1, 1] [1, 2, 1, 0, 1, 0, 1, 2]
5 [1, 1, -1, -1, -1, 1, 1, 1] [1, 2, 1, 0, -1, 0, 1, 2]
6 [1, -1, 1, 1, -1, 1, -1, 1] [1, 0, 1, 2, 1, 2, 1, 2]
7 [1, -1, 1, 1, -1, -1, 1, 1] [1, 0, 1, 2, 1, 0, 1, 2]
8 [1, -1, 1, -1, 1, 1, -1, 1] [1, 0, 1, 0, 1, 2, 1, 2]
9 [1, -1, 1, -1, 1, -1, 1, 1] [1, 0, 1, 0, 1, 0, 1, 2]
10 [1, -1, 1, -1, -1, 1, 1, 1] [1, 0, 1, 0, -1, 0, 1, 2]
11 [1, -1, -1, 1, 1, 1, -1, 1] [1, 0, -1, 0, 1, 2, 1, 2]
12 [1, -1, -1, 1, 1, -1, 1, 1] [1, 0, -1, 0, 1, 0, 1, 2]
13 [1, -1, -1, 1, -1, 1, 1, 1] [1, 0, -1, 0, -1, 0, 1, 2]
14 [-1, 1, 1, 1, -1, 1, -1, 1] [-1, 0, 1, 2, 1, 2, 1, 2]
15 [-1, 1, 1, 1, -1, -1, 1, 1] [-1, 0, 1, 2, 1, 0, 1, 2]
16 [-1, 1, 1, -1, 1, 1, -1, 1] [-1, 0, 1, 0, 1, 2, 1, 2]
17 [-1, 1, 1, -1, 1, -1, 1, 1] [-1, 0, 1, 0, 1, 0, 1, 2]
18 [-1, 1, 1, -1, -1, 1, 1, 1] [-1, 0, 1, 0, -1, 0, 1, 2]
19 [-1, 1, -1, 1, 1, 1, -1, 1] [-1, 0, -1, 0, 1, 2, 1, 2]
20 [-1, 1, -1, 1, 1, -1, 1, 1] [-1, 0, -1, 0, 1, 0, 1, 2]
21 [-1, 1, -1, 1, -1, 1, 1, 1] [-1, 0, -1, 0, -1, 0, 1, 2]

...

print(sum(1 for _ in genCumSum([1]*15+[-1]*12,0,4)))
# 4096

# The last example (with 270 items in the list) would take forever to check

Answer 2

A possible solution would be to use itertools.permutations to generate the permutations, then to check each one.

There are some problems with this approach:

• the number of invalid permutations can be huge, so we'll generate a lot of them for nothing.
• if the first items of a permutation take us out of the bounds, we know that all permutations with the same start will be invalid, but there's no way to make itertools.permutations skip them, so we'll have to generate them anyway
• we have to recompute all of the partial sums for each new permutation.

So, we could rather build the permutations and test them at each step. This way, we can abort a whole branch as soon as an item makes us cross the bounds.

A recursive solution:

 def bounded_permutations(data, lower, upper, start=None, curr_sum=0):
    if start is None:
        start = []
        
    for idx_first, first in enumerate(data):
        new_sum = curr_sum + first
        if not lower < new_sum < upper:
            continue
        new_data = data[:]
        del new_data[idx_first]
        new_start = start + [first]
        if not new_data:  # we used all values in the list!
            yield new_start
        else:
            yield from bounded_permutations(new_data, lower, upper, new_start, new_sum)

Sample run with your data (well, almost, I lost one of the 'A's when copy-pasting):

A=1
B=-1
data = [A, A, A, A, B, B, B]
            
count=0
for p in bounded_permutations(data, 0, 4):
    count += 1
    print(p, count)
    

Output:

[1, 1, 1, -1, 1, -1, -1] 1
[1, 1, 1, -1, 1, -1, -1] 2
[1, 1, 1, -1, -1, 1, -1] 3
[1, 1, 1, -1, -1, 1, -1] 4
[1, 1, 1, -1, 1, -1, -1] 5
.
.
.
[1, 1, -1, 1, -1, 1, -1] 575
[1, 1, -1, 1, -1, 1, -1] 576

Here, we get 576 valid permutations, out of a total of 7! = 5040. We could have counted them with len(list(bounded_permutations(data, 0, 4))) as well.

As there are duplicate values in your data, you'll get many identical permutations. If you want to keep only unique ones, you can use a set. Note that you have to turn the unhashable lists into hashable tuples to use them in a set:

uniques = set(map(tuple, bounded_permutations(data, 0, 4)))
print(uniques)
print('number of unique permutations:', len(uniques))

Output:

{(1, 1, -1, 1, 1, -1, -1), 
 (1, 1, -1, 1, -1, 1, -1),
 (1, 1, 1, -1, 1, -1, -1),
 (1, 1, 1, -1, -1, 1, -1)}
number of unique permutations: 4

Answer 3

You can use itertools to generate permutations and accumulative list. A compact solution which returns the unique permutations whose accumulative list does not contain some specific values is:

import itertools

def contain_specific_value(lst, value_lst):
    return any([True if (item in lst) else False for item in value_lst])

def accumulated_permutations_without_specific_numbers(main_lst, specific_number_lst):
    p = list(itertools.permutations(main_lst, len(main_lst)))
    res = [y for y in p if not contain_specific_value(list(itertools.accumulate(y)), specific_number_lst)]
    return list(set(res))

You just need to pass the certain bound values as a list to the function.

For your list:

A=1
B=-1
my_list = [A, A, A, A, B, B, B]

res = accumulated_permutations_without_specific_numbers(my_list, [0,4])

Output:

(1, 1, 1, -1, -1, 1, -1)
(1, 1, -1, 1, -1, 1, -1)
(1, 1, -1, 1, 1, -1, -1)
(1, 1, 1, -1, 1, -1, -1)

Accumulative lists:

[1, 2, 3, 2, 1, 2, 1]
[1, 2, 1, 2, 1, 2, 1]
[1, 2, 1, 2, 3, 2, 1]
[1, 2, 3, 2, 3, 2, 1]