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>Here is a very simple (and non-optimized) recursive approach:</p>

<h3>Code</h3>

<pre><code>import numpy as np
from time import time

""" PARAMETERS """
SET = range(50) # Set of elements to choose from
N = 6           # N elements to choose
MIN_GAP = 4     # Gaps
MAX_GAP = 7     # ""

def count(N, CHOSEN=[]):
    """ assumption: N &gt; 0 at start """
    if N == 0:
        return 1
    else:
        return sum([count(N-1, CHOSEN + [val])
                        for val in SET if (val not in CHOSEN)
                                       and ((not CHOSEN) or ((val - CHOSEN[-1]) &gt;= MIN_GAP))
                                       and ((not CHOSEN) or ((val - CHOSEN[-1]) &lt;= MAX_GAP))])

start_time = time()
count_ = count(N)
print('used time in secs: ', time() - start_time)
print('# solutions: ', count_)
</code></pre>

<h3>Output</h3>

<pre><code>('used time in secs: ', 0.1174919605255127)
('# solutions: ', 23040)
</code></pre>

<h3>Remarks</h3>

<ul>
<li>It outputs the same solution as Ayman's approach</li>
<li><strong>Ayman's approach is much more powerful (in terms of asymptotical speed)</strong></li>
</ul>

python algorithm combinatorics itertools