Number of combinations less than 100

Viewed 438

I have 13 lists belonging to different groups:

  • Group A (List 1)

  • Group B (List 2), (List 3), (List 4), (List 5), (List 6)

  • Group C (List 7), (List 8), (List 9), (List 10), (List 11)

  • Group D (List 12), (List 13)

All of the groups together must sum up to 1

  • Group A can take values from 0-0.7

  • Group B can take values from 0-0.6

  • Group C can take values from 0-0.9

  • Group D can take values from 0-0.1

I want to find all different combinations that these lists can make without exceeding limits of their group.

For example:

if for one combination List2 element = 0.6, List3, List4, List5 and List6 must be 0

Is there an easy way to do that? (I can use R or Python)

(The lists take values from 0 to their Group's limit with an increment of .1)

# i.e. 
List1=[0.0,0.1,0.2,...,0.7]
List2 = [0.0,0.1,0.2,...,0.6]
# etc.
3 Answers

As suggested in my comment we can use Google OR-Tools which are meant for optimization problems such as this. I will try to break down each step to make it as clear as possible and show how this can extend to fit your needs.

from ortools.sat.python import cp_model
model = cp_model.CpModel()

class Data:
    def __init__(self, name, ub, model):
        self.name = name
        self.ub = ub
        self.model = model

    def make_var(self, repeat):
        vars = [self.model.NewIntVar(0, self.ub, f"{self.name}{i}") for i in range(repeat)]
        return vars

We define a class, Data which will hold information about each of your arrays. It will contain the name, the upper bound, and the reference to the model where this variable will be used on. We also define a function, make_var which will create an integer variable for the model to solve for.

If you think about it from the highest level your model really comes down to the following constraint:

a + b1 + b2 + b3 + b4 + b5 + c1 + c2 + c3 + c4 + c5 + d1 + d2 == 100

Each group of array's has its own condition to fulfill but from the highest level this is what we are trying to solve for. make_var will create each of these variables and attach it to the model. This is shown below.

# Variables
a = Data("a", 70, model)
var_a = a.make_var(1)

b = Data("b", 60, model)
var_b = b.make_var(5)

c = Data("c", 90, model)
var_c = c.make_var(5)

d = Data("d", 10, model)
var_d = d.make_var(2)

Next we will add our constraints which each group of arrays is subject to.

# Constraints
model.Add(sum(var_a) <= 70)
model.Add(sum(var_b) <= 60)
model.Add(sum(var_c) <= 90)
model.Add(sum(var_d) <= 10)
model.Add(sum(var_a) + sum(var_b) + sum(var_c) + sum(var_d) == 100)

After that we will define a class which will print our solutions as well as cap the limit on the number of solutions we want to return. That is configureable and you can change that however it makes sense to you. This class is a modified version of the class which can be found here.

class VarArraySolutionPrinterWithLimit(cp_model.CpSolverSolutionCallback):
    """Print intermediate solutions."""

    def __init__(self, variables, limit):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self.__variables = variables
        self.__solution_count = 0
        self.__solution_limit = limit

    def on_solution_callback(self):
        self.__solution_count += 1
        for v in self.__variables:
            for val in v:
                print('%s = %i' % (val, self.Value(val)), end=' ')
        print()
        if self.__solution_count >= self.__solution_limit:
            print('Stop search after %i solutions' % self.__solution_limit)
            self.StopSearch()

    def solution_count(self):
        return self.__solution_count

Lastly we solve for the solutions to your problem.

solver = cp_model.CpSolver()
solution_printer = VarArraySolutionPrinterWithLimit([var_a, var_b, var_c, var_d], 10)
status = solver.SearchForAllSolutions(model, solution_printer)

a0 = 0 b0 = 10 b1 = 0 b2 = 0 b3 = 0 b4 = 0 c0 = 0 c1 = 0 c2 = 90 c3 = 0 c4 = 0 d0 = 0 d1 = 0 
a0 = 0 b0 = 9 b1 = 0 b2 = 0 b3 = 0 b4 = 0 c0 = 0 c1 = 0 c2 = 90 c3 = 0 c4 = 0 d0 = 1 d1 = 0 
a0 = 0 b0 = 60 b1 = 0 b2 = 0 b3 = 0 b4 = 0 c0 = 0 c1 = 0 c2 = 30 c3 = 0 c4 = 0 d0 = 10 d1 = 0 
a0 = 0 b0 = 60 b1 = 0 b2 = 0 b3 = 0 b4 = 0 c0 = 0 c1 = 0 c2 = 30 c3 = 0 c4 = 0 d0 = 9 d1 = 1 
a0 = 0 b0 = 0 b1 = 0 b2 = 0 b3 = 0 b4 = 0 c0 = 0 c1 = 0 c2 = 90 c3 = 0 c4 = 0 d0 = 0 d1 = 10 
a0 = 0 b0 = 0 b1 = 1 b2 = 0 b3 = 0 b4 = 0 c0 = 0 c1 = 0 c2 = 90 c3 = 0 c4 = 0 d0 = 0 d1 = 9 
a0 = 0 b0 = 0 b1 = 0 b2 = 1 b3 = 0 b4 = 0 c0 = 0 c1 = 0 c2 = 90 c3 = 0 c4 = 0 d0 = 0 d1 = 9 
a0 = 0 b0 = 0 b1 = 0 b2 = 0 b3 = 1 b4 = 0 c0 = 0 c1 = 0 c2 = 90 c3 = 0 c4 = 0 d0 = 0 d1 = 9 
a0 = 0 b0 = 0 b1 = 0 b2 = 0 b3 = 0 b4 = 1 c0 = 0 c1 = 0 c2 = 90 c3 = 0 c4 = 0 d0 = 0 d1 = 9 
a0 = 0 b0 = 1 b1 = 0 b2 = 0 b3 = 0 b4 = 0 c0 = 0 c1 = 0 c2 = 90 c3 = 0 c4 = 0 d0 = 0 d1 = 9 
Stop search after 10 solutions

I set the limit to 10 solutions but as mentioned previously you can change this as needed. It took ~9ms to obtain the solutions so this should work efficiently and quickly for your use-case.

(I am using ints rather than floats so that e.g. 4 stands for 4%)

The basic idea is to find 4 numbers a,b,c,d (where each satisfies the group bound) which sums to 100. I did this part by brute force, but it could be optimized. Then, for each such list of 4 numbers, combine a with all of the ways to pick 5 numbers which sum to b, all of the ways to pick 5 numbers which sum to c, and all of the ways to pick 2 numbers which sum to d. I don't want to get into the math too much, but see the Wikipedia article on Stars and bars to unpack the following code, which contains both a function to count the combinations and a generator for generating them.

import itertools, math

def count_combos():
    count = 0
    for a,b,c,d in itertools.product(range(71),range(61),range(91),range(11)):
        if a+b+c+d == 100:
            count += math.comb(b+4,4)*math.comb(c+4,4)*(d+1)
    return count

#uses stars and bars to enumerate k-tuples of nonnegative numbers which sum to n:
#assumes k > 1

def terms(n,k):
    for combo in itertools.combinations(range(n+k-1),k-1):
        s = [combo[0]]
        for i in range(1,k-1):
            s.append(combo[i]-combo[i-1]-1)
        s.append(n+k - 2 - combo[k-2])
        yield s

def all_combos():
    for a,b,c,d in itertools.product(range(71),range(61),range(91),range(11)):
        if a+b+c+d == 100:
            for p in terms(b,5):
                for q in terms(c,5):
                    for r in terms(d,2):
                        yield [a]+p+q+r

For the number of solutions: count_combos() evaluates to 1470771090600747, which is roughly 1.5 quadrillion. Note that this function requires Python 3.8 since it uses the recently added math.comb.

It is infeasible to actually use the generator in its totality, but, for example:

import random
some_combos = [list(c) for c in itertools.islice(all_combos(),1000000)]
for _ in range(5): print(random.choice(some_combos))

Typical output:

[0, 0, 0, 0, 0, 2, 0, 13, 13, 32, 31, 8, 1]
[0, 0, 0, 0, 0, 2, 0, 5, 36, 28, 20, 6, 3]
[0, 0, 0, 0, 0, 2, 0, 8, 42, 16, 23, 4, 5]
[0, 0, 0, 0, 0, 2, 0, 13, 42, 12, 22, 1, 8]
[0, 0, 0, 0, 0, 2, 0, 10, 69, 7, 3, 8, 1]

On Edit There was a bug in my first implementation of count_combos which I fixed. Beyond that, I'll keep the answer as is. It was referring to an earlier version of the question where there was e.g. 71 possibilities for group A rather than just 8. This answer underscores that increments of 1% lead to an infeasible number of solutions. When I tweak the code so that e.g. range(71) becomes range(8), I get the exact same counts as Arne does in their answer.

Answer edited according to new question


You could use list comprehensions, which are reasonably fast. The following code only took a few seconds on my PC. I used John Coleman's idea to first find the possible combinations of sums per group. I also used integers rather than floats. To transform the solutions back to the problem as stated in the question, divide every list value by 10.

from itertools import product

A = range(8)  # 1 value from this group
B = range(7)  # 5 values from this group (with replacement)
C = range(10) # 5 values from this group (with replacement)
D = range(2)  # 2 values from this group (with replacement)

# use John Coleman's idea:
# first find all possible combinations of sums per group
groupsums = [sums for sums in product(A, B, C, D) if sum(sums) == 10]
print(len(groupsums))  # -> 95

def picks(maxi, n):
    """Returns list of combinations of n integers <= maxi 
       that sum to maxi."""
    return [combi for combi in product(range(maxi + 1), repeat=n)
                  if sum(combi) == maxi]

# make list of lists that each have 13 items from the above ranges, 
# with constraints as stated in the question
samples = [[a, b0, b1, b2, b3, b4, c0, c1, c2, c3, c4, d0, d1] 
           for a, b, c, d in groupsums
           for b0, b1, b2, b3, b4 in picks(b, 5)
           for c0, c1, c2, c3, c4 in picks(c, 5)
           for d0, d1 in picks(d, 2)]

# show the first 5 and last 5 results
for i in range(5):
    print(samples[i])
print('...')
for i in range(1, 6):
    print(samples[-i])

# show the number of solutions
print(len(samples))
95
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 0, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 8, 0, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 8, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 7, 0, 1]
...
[7, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[7, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[7, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[7, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[7, 2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
313027
Related