python - 计算彼此之间具有最小和最大差异的唯一正整数的组合数？

Question

我如何编写一个 Python 程序来计算可以选择的整数范围内唯一排序正整数的组合数，其中集合中每个数字之间的最小差是一个数字，最大差是另一个号码？

例如，如果我想计算我可以从 1-50 的正整数中选择 6 个数字的方式的数量，使得每个数字之间的最小差为 4，每个数字之间的最大差为 7，我会想计算 {1,6,12,18,24,28} 的组合，因为最小差为 4，最大差为 6，但我不想计算 {7,19,21,29,41 这样的组合,49}，因为最小差值为 2，最大差值为 12。

到目前为止我有以下代码，但问题是它必须循环遍历每个组合，在很多情况下这会花费非常长的时间。

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

我没有组合学背景，但我猜有一种算法效率更高的方法可以使用一些组合方法来做到这一点。

Answer 1

您可以使用带缓存的递归函数来获得答案。即使您有一个大数组，此方法也适用，因为某些位置使用相同的参数重复多次。
这是给你的代码(如果我在 python 中犯了任何错误，请原谅我，因为我通常不使用它)。如果逻辑上有任何流程，请告诉我

# 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