给定一个包含 20 个浮点数的列表,我想找到一个最大的子集,其中任意两个候选者彼此不同,大于 mindiff = 1.
.现在我正在使用蛮力方法使用 itertools.combinations
从最大到最小的子集进行搜索。 .如下图,代码在 4 s 后为 20 个数字的列表找到了一个子集。
from itertools import combinations
import random
from time import time
mindiff = 1.
length = 20
random.seed(99)
lst = [random.uniform(1., 10.) for _ in range(length)]
t0 = time()
n = len(lst)
sample = []
found = False
while not found:
# get all subsets with size n
subsets = list(combinations(lst, n))
# shuffle to ensure randomness
random.shuffle(subsets)
for subset in subsets:
# sort the subset numbers
ss = sorted(subset)
# calculate the differences between every two adjacent numbers
diffs = [j-i for i, j in zip(ss[:-1], ss[1:])]
if min(diffs) > mindiff:
sample = set(subset)
found = True
break
# check subsets with size -1
n -= 1
print(sample)
print(time()-t0)
输出:{2.3704888087015568, 4.365818049020534, 5.403474619948962, 6.518944556233767, 7.8388969285727015, 9.117993839791751}
4.182451486587524
但是,实际上我有一个包含 200 个数字的列表,这对于粗暴枚举是不可行的。我想要一个快速算法来采样一个 随机 最大最小差异大于 1 的子集。请注意,我希望每个样本都具有随机性和最大大小。有什么建议么?
最佳答案
我之前的回答假设您只想要一个最佳解决方案,而不是所有解决方案的统一随机样本。这个答案假设您想要一个从所有这些最佳解决方案中统一采样的答案。
G
其中每个点有一个节点,节点 a
和 b
连接时 b - a > mindist
.同时添加两个虚拟节点,s
和 t
,其中 s -> x
所有 x
和 x -> t
所有 x
.G
中的每个节点多少条路径长度k
存在于 t
.您可以在 O(n^2 k)
中有效地执行此操作使用带有表的动态规划的时间 P[x][k]
, 初步填写 P[x][0] = 0
除了 P[t][0] = 1
,然后 P[x][k] = sum(P[y][k-1] for y in neighbors(x))
.继续这样做,直到达到最大值
k
- 您现在知道最佳子集的大小。k
的路径来自 s
至 t
使用 P
来衡量你的选择。这是通过从
s
开始来完成的。 .然后我们查看s
的每个邻居并随机选择一个权重由 P[s][k]
决定的.这给了我们最优集合的第一个元素。然后我们重复执行这一步。我们在
x
,看x
的邻居并使用权重随机选择一个 P[x][k-i]
哪里i
是我们的步骤。在纯 Python 中实现上述内容:
import random
def sample_mindist_subset(xs, mindist):
# Construct directed graph G.
n = len(xs)
s = n; t = n + 1 # Two virtual nodes, source and sink.
neighbors = {
i: [t] + [j for j in range(n) if xs[j] - xs[i] > mindist]
for i in range(n)}
neighbors[s] = [t] + list(range(n))
neighbors[t] = []
# Compute number of paths P[x][k] from x to t of length k.
P = [[0 for _ in range(n+2)] for _ in range(n+2)]
P[t][0] = 1
for k in range(1, n+2):
for x in range(n+2):
P[x][k] = sum(P[y][k-1] for y in neighbors[x])
# Sample maximum length path uniformly at random.
maxk = max(k for k in range(n+2) if P[s][k] > 0)
path = [s]
while path[-1] != t:
candidates = neighbors[path[-1]]
weights = [P[cn][maxk-len(path)] for cn in candidates]
path.append(random.choices(candidates, weights)[0])
return [xs[i] for i in path[1:-1]]
请注意,如果您想从同一组数字中多次采样,则不必重新计算 P
每次都可以重复使用。
关于python - 以最小差异大于 Python 列表中的值对大多数数字进行采样的最快方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/68039647/