Calculate the number of combinations of unique positive integers with minimum and maximum differences between each other?

0
votes

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?

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.

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.

import itertools

def min_max_differences(integer_list):
    i = 1
    diff_min = max(integer_list)
    diff_max = 1
    while i < len(integer_list):
        diff = (integer_list[i]-integer_list[i-1])
        if diff < diff_min:
            diff_min = diff
        if diff > 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] >= min_difference and min_max_differences(c)[1] <= max_difference:
            min_max_diff_combos += 1
    return min_max_diff_combos

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.

2
pythonalgorithmcombinatoricsitertools
Try an recursive-algorithm wird forward-pruning. When doing the recursion-step, you are chosing every next number to add: there you can do the checks, if it's feasible to add this element. – sascha
By the way: this problem is very hard. Just imagine an instance, where the number of solutions is growing exponentially. What are your instances like? Values for set-size, number-of-chosings, min-gap, max-gap? – sascha
Update My hardness-approximation from above was based on the assumption, that the gaps are restrictive for each pairs of chosen values. Although you used the phrasing the minimum difference between each number, i know understood what you really wanted (just restrict neighbors). – sascha

2 Answers

1
votes

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.
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

# 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 < len(numbers) and numbers[p] - pivot < min:
        p += 1

    # get all the values in the range of min <--> max
    while p < len(numbers) and numbers[p] - pivot <= 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
0
votes

Here is a very simple (and non-optimized) recursive approach:

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 > 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]) >= MIN_GAP))
                                       and ((not CHOSEN) or ((val - CHOSEN[-1]) <= MAX_GAP))])

start_time = time()
count_ = count(N)
print('used time in secs: ', time() - start_time)
print('# solutions: ', count_)

Output

('used time in secs: ', 0.1174919605255127)
('# solutions: ', 23040)

Remarks

  • It outputs the same solution as Ayman's approach
  • Ayman's approach is much more powerful (in terms of asymptotical speed)