以最小差异大于Python列表中的值对大多数数字进行采样的最快方法

html5 • • 问答

给定一个包含 20 个浮点数的列表，我想找到一个最大的子集，其中任意两个候选者彼此不同且大于 a 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 的随机 最大子集进行采样。请注意，我希望每个样本都具有随机性和最大大小。有什么建议？

回答

我之前的回答假设您只想要一个最佳解决方案，而不是所有解决方案的统一随机样本。这个答案假设您想要一个从所有这些最佳解决方案中统一采样的答案。

  1. 构造一个有向无环图G，其中每个点有一个节点，当 时节点a和b连通b - a > mindist。还要添加两个虚拟节点s和t， where s -> xfor allx和x -> tfor all x。

  2. 计算每个节点存在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- 您现在知道最佳子集的大小。

  3. 均匀样品长度的路径k从s到t使用P体重您的选择。

    这是通过从 开始完成的s。然后我们查看 的每个邻居s并随机选择一个，权重由 决定P[s][k]。这给了我们最优集合的第一个元素。

    然后我们重复执行这一步。我们在x，查看 的邻居x并使用权重随机选择一个我们P[x][k-i]所处i的步骤。

  4. 使用您在 3 中采样的节点作为您的随机子集。

在纯 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每次都重新计算并且可以重复使用它。

回答

我可能不完全理解这个问题，因为现在解决方案非常简单。编辑：是的，毕竟我误解了，OP 不仅想要一个最佳解决方案，而且希望从一组最佳解决方案中随机抽样。这个答案并没有错，但它也是对与 OP 感兴趣的问题不同的问题的答案。

简单地对数字进行排序并贪婪地构造子集：

def mindist_subset(xs, mindist):
    result = []
    for x in sorted(xs):
        if not result or x - result[-1] > mindist:
            result.append(x)
    return result

正确性证明草图。

假设我们有一个S给定输入数组A的最佳大小的解决方案。如果它不包含min(A)音符，我们可以删除min(S)从S添加min(A)，因为这只会增加之间的距离min(S)，并在第二小的数字S。结论：我们可以不失一般性地假设它min(A)是最优解的一部分。

现在我们可以递归地应用这个论点。我们添加min(A)到一个解决方案并删除所有太接近的元素min(A)，给出剩余的元素A'。然后我们剩下一个子问题，其中应用完全相同的参数，我们可以选择min(A')作为解决方案的下一个元素，等等。

  • @ShaunHan Your problem becomes a lot more interesting if you wish to sample uniformly at random from all optimal subsets, which was one possible interpretation I had of your question when I said "I probably don't fully understand the question".
以上是以最小差异大于Python列表中的值对大多数数字进行采样的最快方法的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>