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?
There's no docstring. How do I use this function? What arguments do I pass? What does it return?
It would be very easy to make this code portable to Python 3: just put parentheses around the argument to print.
There's no need to terminate a statement with a semicolon in Python.
The name func does not give any hint as to what the function might do. A name like combinations_with_gap would be clearer.
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)

If you're just counting combinations (rather than generating the combinations themselves), then you don't need the array variable, just its length.
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)

This runs in just over 4 seconds on my computer:

&gt;&gt;&gt; from timeit import timeit
&gt;&gt;&gt; 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:

&gt;&gt;&gt; timeit(lambda:combinations_with_gap(6, 50, 3), number=1)
0.0017554410151205957