# Count the number of combinations with gap-restriction for every pair of values

A lottery draw consists of choosing 6 different values from 1 to 50.

I want to calculate the number of combinations with gaps of at least 3 between every pair of values.

I have used the following Python 2.7 script:

def func(array,length,min,max,gap):
if len(array) == length:
# print array
return 1
count = 0
for n in range(min,max+1):
count += func(array+[n],length,n+gap,max,gap)
return count;

print func([],6,1,50,3)


Questions:

• Are there any coding improvements that I can apply?
• Is there a different method with which we can do it more efficiently?
• Although more suitable for math.stackexchange.com, is there a straightforward formula?
• When I run your script, I get TypeError: func() missing 2 required positional arguments – Gareth Rees Jun 20 '15 at 9:31
• @GarethRees: Sorry, I initially had length and gap hard-coded in the function. I changed them to be function arguments after I had already posted the question, but I forgot that the function itself was recursive (so the recursive call consisted of 3 instead of 5 parameters). Thanks for pointing that out. – barak manos Jun 20 '15 at 9:39

1. There's no docstring. How do I use this function? What arguments do I pass? What does it return?

2. It would be very easy to make this code portable to Python 3: just put parentheses around the argument to print.

3. There's no need to terminate a statement with a semicolon in Python.

4. The name func does not give any hint as to what the function might do. A name like combinations_with_gap would be clearer.

5. When you have code that accumulates a sum like this:

count = 0
for n in A:
count += B


you can use the built-in sum:

count = sum(B for n in A)

6. If you're just counting combinations (rather than generating the combinations themselves), then you don't need the array variable, just its length.

7. Presumably the caller is supposed to always pass the empty list [] for array and 1 for min. In that case, why make them do it? It would be easier for the caller if the function just took the arguments you need, and used a local function to do the work, like this:

def combinations_with_gap(k, max, gap):
"""Return the number of ways of choosing k of the numbers from 1 to
max such that no two numbers are closer than gap.

"""
def c(length, min):
if length == k:
return 1
return sum(c(length + 1, n + gap) for n in range(min, max + 1))
return c(0, 1)

8. This runs in just over 4 seconds on my computer:

>>> from timeit import timeit
>>> timeit(lambda:combinations_with_gap(6, 50, 3), number=1)
4.182408502034377


Where is it spending its time? If you trace the calls to the inner function c, you'll see that the same values for length and min occur many times. This is a waste of effort: having computed c(5, 44), say, it would be a good idea to remember the result and reuse it instead of computing it again.

One way to do this is to memoize the function, for example using the @functools.lru_cache decorator:

from functools import lru_cache

def combinations_with_gap(k, max, gap):
"""Return the number of ways of choosing k of the numbers from 1 to
max such that no two numbers are closer than gap.

"""
@lru_cache(maxsize=None)
def c(length, min):
if length == k:
return 1
return sum(c(length + 1, n + gap) for n in range(min, max + 1))
return c(0, 1)


This version takes just a couple of milliseconds:

>>> timeit(lambda:combinations_with_gap(6, 50, 3), number=1)
0.0017554410151205957

• Thank you very much. 3. Ooops, I thought I had removed all of those semicolons (C habit). 5. I think that this would create a huge (temporary) array at some point, so I'm not sure it is such a good idea. 6. As implied by the # print array, I wanted to be able to easily generate those combinations. 8. So I guess that you're implying towards an iterative solution (a.k.a dynamic programming) instead of the recursive one? – barak manos Jun 20 '15 at 10:22
• 5. No array is created: B for n in A is a generator expression. 6. If you want fast counting of combinations, but also want to generate the combinations, then you need two different functions. 8. Yes: recursion plus memoization is a form of dynamic programming, but no: I don't suggest you use an iterative solution (recursion plus memoization is usually clearer). – Gareth Rees Jun 20 '15 at 10:28
• Thank you, this is a very good answer (in particularly the last section)! – barak manos Jun 20 '15 at 10:29

Give your function a more descriptive name, gapped_lottery is not great but better than func.

Use an underscore after min and max to avoid shadowing built-ins.

Use a generator comprehension to shorten the code:

def gapped_lottery(array,length,min_,max_,gap):
if len(array) == length:
return 1
return sum(gapped_lottery(array+[n],length,n+gap,max_,gap)
for n in range(min_, max_ + 1))


Omit the semicolon after return;

• Thank you very much. 1. Did it with length (instead of len), but forgot about min and max being built-ins. 2. I think that the generator would create a huge (temporary) array at some point, so I'm not sure it is such a good idea. In any case, I think it makes it less readable. 3. Ooops, I thought I had removed all of those semicolons (C habit). – barak manos Jun 20 '15 at 10:15
• Can you explain what's wrong with shadowing built-ins here? The code does not use the built-in min or max, so what's the problem? – Gareth Rees Jun 20 '15 at 10:18
• @barakmanos generators are lazy, they generate the value as needed one by one, with no memory penalty. I think a generator is more readable but that depends on one's background. – Caridorc Jun 20 '15 at 10:20
• @GarethRees in this case shadowing built-ins (that is: making it impossible to call native functions by naming something other as them) is a little problem, but I think that the habit of always avoiding them can avoid name conflicts at little cost. – Caridorc Jun 20 '15 at 10:21