Calculate the number of combinations of unique positive integers with minimum and maximum differences between each other?
<p>How do I write a Python program to calculate the number of combinations of unique sorted positive integers over a range of integers that can be selected where the minimum difference between each of the numbers in the set is one number and the maximum difference is another number?</p>

<p>For instance, if I want to calculate the number of ways I can select 6 numbers from the positive integers from 1-50 such that the minimum difference between each number is 4 and the maximum difference between each number is 7, I would want to count the combination {1,6,12,18,24,28} since the minimum difference is 4 and the maximum difference is 6, but I would not want to count combinations like {7,19,21,29,41,49} since the minimum difference is 2 and the maximum difference is 12.</p>

<p>I have the following code so far, but the problem is that it has to loop through every combination, which takes an extremely long time in many cases.</p>

<pre><code>import itertools

def min_max_differences(integer_list):
    i = 1
    diff_min = max(integer_list)
    diff_max = 1
    while i &lt; len(integer_list):
        diff = (integer_list[i]-integer_list[i-1])
        if diff &lt; diff_min:
            diff_min = diff
        if diff &gt; diff_max:
            diff_max = diff
        i += 1
    return (diff_min,diff_max)

def total_combinations(lower_bound,upper_bound,min_difference,max_difference,elements_selected):
    numbers_range = list(range(lower_bound,upper_bound+1,1))
    all_combos = itertools.combinations(numbers_range,elements_selected)
    min_max_diff_combos = 0
    for c in all_combos:
        if min_max_differences(c)[0] &gt;= min_difference and min_max_differences(c)[1] &lt;= max_difference:
            min_max_diff_combos += 1
    return min_max_diff_combos
</code></pre>

<p>I do not have a background in combinatorics, but I am guessing there is a much more algorithmically efficient way to do this using some combinatorial methods.</p>

<p>You can use a recursive function with caching to get your answer.
This method will work even if you have a large array because some positions are repeated many times with the same parameters.<br>
Here is a code for you (forgive me if I made any mistakes in python cause I don't normally use it).
If there is any flow in the logic, please let me know</p>

<pre><code># function to get the number of ways to select {target} numbers from the 
# array {numbers} with minimum difference {min} and maximum difference {max}
# starting from position {p}, with the help of caching

dict = {}
def Combinations(numbers, target, min, max, p):
    if target == 1: return 1

    # get a unique key for this position
    key = target * 1000000000000 + min * 100000000 + max * 10000 + p

    if dict.has_key(key): return dict[key]

    ans = 0

    # current start value
    pivot = numbers[p]
    p += 1;
    # increase the position until you reach the minimum
    while p &lt; len(numbers) and numbers[p] - pivot &lt; min:
        p += 1

    # get all the values in the range of min &lt;--&gt; max
    while p &lt; len(numbers) and numbers[p] - pivot &lt;= max:
        ans += Combinations(numbers, target - 1, min, max, p)
        p += 1

    # store the ans for further inquiry
    dict[key] = ans
    return ans


# any range of numbers (must be SORTED as you asked)
numbers = []
for i in range(0,50): numbers.append(i+1)
# number of numbers to select
count = 6
# minimum difference
min = 4
# maximum difference
max = 7
ans = 0
for i in range(0,len(numbers)):
    ans += Combinations(numbers, count, min, max, i)
print ans
</code></pre>

python algorithm combinatorics itertools