假設我有一個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子集
return None
例如，如果我想得到一個數字相差至少6的5的子集：
。subset = k_subset_at_least_d_apart(lst, k=5, d=6)
print(subset)
# (1, 10, 20, 27, 40)。
但是，當我想從一個50個數字的串列中獲取20個數字的子集時，我的代碼變得太慢了，因為其中的數字至少相差10個。誰能推薦一種相對快速的演算法，首先確定這種子集是否存在，然后找到一個子集？預先感謝。
uj5u.com熱心網友回復：
當然，你可以貪婪地重復取最小的有效元素的步驟：
def k_subset_at_least_d_apart（nums, k, d）。
Last = -float('inf')
回答 = []
for element in sorted（nums）。
if element - last >= d:
answer.append(element)
最后=元素
if len(answer) == k:
return答案。
return None
如果nums沒有被預排序，很難做到（漸進地）比這段代碼好得多，它需要O(n log n)時間。如果它們被排序了，你可以做 "貪婪地取最小有效元素"，但是要通過二進制搜索來找到下一個最小的有效元素，以達到O(k log n)的演算法。
貪婪演算法的證明：
假設貪婪演算法給出了一個解決方案G = g0, g1, ... gm，并且一個最優（長度-k）的解決方案由A = a0, a1, ... a_(k-1)給出，其中m <= k-1（都是按排序的，增加的順序）。
設i為最小的索引，其中ai != gi。如果i為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。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/326062.html
標籤：
下一篇：svg的背景顏色