从相距至少d的数字列表中获取k子集的有效方法？

Question

假设我有一个10个数字的列表，如下所示

lst = [1, 3, 6, 10, 15, 20, 27, 28, 30, 40]

我想得到k个数的一个子集，其中每对数之间至少有一段距离d。现在我正在使用itertools.combinations，代码对于小列表来说运行良好

from itertools import combinations

def k_subset_at_least_d_apart(nums, k, d):
    for subset in combinations(nums, k):
        a = sorted(subset)
        if min([t - s for s, t in zip(a, a[1:])]) >= d:
            return subset
    return None

例如，如果我想得到一个5的子集，其中数字之间的间隔至少为6：

subset = k_subset_at_least_d_apart(lst, k=5, d=6)
print(subset)
# (1, 10, 20, 27, 40)

但是，当我想从50个数字的列表中获取20个数字的子集时，我的代码会变得太慢，其中的数字至少相隔10个。有人能提出一个相对快速的算法，首先确定这样的子集是否存在，然后找到一个子集吗？提前谢谢

Answer 1

当然；您可以贪婪地重复使用最小有效元素的步骤：

def k_subset_at_least_d_apart(nums, k, d):
    last = -float('inf')
    answer = []
    for element in sorted(nums):
        if element - last >= d:
            answer.append(element)
            last = element
            if len(answer) == k:
                return answer
    return None

如果NUM没有预先分类，那么很难（渐进地）比这段代码做得更好，因为这段代码需要O(n log n)时间。您可以得到一个具有k个重复过程的O(n*k)算法，这可能会更快，具体取决于n和k。如果对它们进行了排序，您可以执行“greedily take min valid”，但要使用二进制搜索来查找下一个最小的有效元素，即O(k log n)算法

贪婪算法的证明：

假设贪心算法给出了一个解G = g0, g1, ... gm，最优（长度k）解由A = a0, a1, ... a_(k-1)给出，其中m <= k-1（都是按排序的递增顺序）

设i为最小索引，其中ai != gi。如果我是0，我们必须有g0 < a0，因为g0是min(nums)，所以我们可以在A中用g0替换a0，以获得另一个最优解A' = g0, a1, ... a_(k-1)。否则，对于i>；0，（详细信息作为练习保留，但与上面非常类似），如果a0 == g0, a1 == g1 ... a_(i-1)==g_(i-1)，我们还可以用gi替换ai，以获得另一个最佳解决方案

最终我们得到存在一个最优解A*，使得G是A*的前缀，然后我们可以矛盾地论证，如果G的长度小于k，并且是最优解的适当前缀，贪婪算法在看到元素a_(m+1)时会扩展G