Issue

This Content is from Stack Overflow. Question asked by ZooPanda

Say you are given a range of numbers,
[1,2,3] where r = 3

and you are required to find the number of combinations of numbers that can be formed given a min and max group size. For example,

min = 1
max = 3

Can have the following configurations:

Config 1: [1, 2, 3]  
Config 2: [1, 2] [3] 
Config 3: [1, 3] [2] 
Config 4: [2, 3] [1] 
Config 5: [1] [2, 3] 
Config 6: [2] [1, 3] 
Config 7: [3] [1, 2] 
Config 8: [1] [2] [3] 
Config 9: [1] [3] [2] 
Config 10: [2] [1] [3] 
Config 11: [2] [3] [1] 
Config 12: [3] [1] [2] 
Config 13: [3] [2] [1]

More examples:

r = 7, min = 2, max = 7

will yield 1730

r = 7, min = 2, max = 3

will yield 1400 as

[1,2,3], [4,5,6] 3 3 = ncr(7,3) * ncr(4, 3) = 140
[1,2,3], [4,5], [6,7] 3 2 2 = ncr(7,3) * ncr(4, 2) * 3 = 630
[1,2], [3,4], [5,6] 2 2 2 = ncr(7,2) * ncr(5, 2) * ncr(3, 2) = 630

and

r = 7, min = 2, max = 2

will yield 630 as

(ncr(7,2) * ncr(5, 2) * ncr(3,2))

This gets progressively more difficult as the numbers get larger. The question is, how do i write something generate that can cover these cases? I cannot wrap my head around the combinations and permutations for this.

Solution

I’m skeptical that, with three parameters, there’s a nice closed form, but the memoized recursive function below should do the trick.

import functools
import math


@functools.cache
def count(r, min, max):
    if r < 0:
        return 0
    if r < min:
        return 1
    return sum(math.comb(r, k) * count(r - k, min, max) for k in range(min, max + 1))


if __name__ == "__main__":

    def test(r, min, max):
        print("X={}, Y={}, Z={} --> {}".format(r, min, max, count(r, min, max)))

    test(3, 1, 3)
    test(7, 2, 7)
    test(7, 2, 3)
    test(7, 2, 2)

Output:

X=3, Y=1, Z=3 --> 13
X=7, Y=2, Z=7 --> 1730
X=7, Y=2, Z=3 --> 1400
X=7, Y=2, Z=2 --> 630

This Question was asked in StackOverflow by ZooPanda and Answered by David Eisenstat It is licensed under the terms of CC BY-SA 2.5. - CC BY-SA 3.0. - CC BY-SA 4.0.