title: Efficient way to get a k-subset from a list of numbers in which numbers are at least d apart?
body: <p>Say I have a list of 10 numbers as below</p>
  <pre><code>lst = [1, 3, 6, 10, 15, 20, 27, 28, 30, 40]
  </code></pre>
  <p>I want to get <strong>one</strong> subset of <code>k</code> numbers, in which every pair of numbers are at least different from each other by a distance <code>d</code>. Right now I am using <code>itertools.combinations</code>, and the code is working fine for small lists.</p>
  <pre><code>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:])]) &gt;= d:
              return subset
      return None
  </code></pre>
  <p>For example, if I want to get a subset of 5 with numbers at least 6 apart from each other:</p>
  <pre><code>subset = k_subset_at_least_d_apart(lst, k=5, d=6)
  print(subset)
  # (1, 10, 20, 27, 40)
  </code></pre>
  <p>However, my code becomes too slow when I want to e.g. get a subset of 20 numbers from a list of 50 numbers in which numbers are at least 10 apart. Can anyone suggest a relatively fast algorithm that can first determine whether such subset exists or not, then finds one subset? Thanks in advance.</p>