从有序列表生成随机子列表以维护排序

Question

考虑一个问题,其中必须从X中选择k个项目的随机子列表Y,n个项目的列表,其中Y中的项目必须以与它们在X中相同的顺序出现.Y中的所选项目不必是不同.一个解决方案是:

for i = 1 to k
    A[i] = floor(rand * n) + 1
    Y[i] = X[A[i]]
sort Y according to the ordering of A

但是,由于排序操作,它具有运行时间O(k log k).要删除它,它很诱人

high_index = n
for i = 1 to k
    index = floor(rand * high_index) + 1
    Y[k - i + 1] = X[index]
    high_index = index

但由于统一的索引选择,这给返回列表提供了明显的偏差.如果第二溶液中的指数非均匀分布,则感觉可以获得O(k)溶液.有没有人知道是否是这种情况,如果是这样,边际指数的分布具有哪些属性？

Answer 1

对于 Y 中的第一个索引，X 中的索引分布由下式给出：

P(x; n, k) = 二项式(n - x + k - 2, k - 1) / 范数

其中binomial表示二项式系数的计算，norm是归一化因子，等于可能的子列表配置的总数。

范数 = 二项式(n + k - 1, k)

因此，对于 k = 5 和 n = 10，我们有：

• 标准 = 2002 年
• P(x = 0) = 0.357, P(x <= 0) = 0.357
• P(x = 1) = 0.245, P(x <= 1) = 0.604
• P(x = 2) = 0.165, P(x <= 2) = 0.769
• P(x = 3) = 0.105, P(x <= 3) = 0.874
• P(x = 4) = 0.063, P(x <= 4) = 0.937
• ...（我们可以继续这个直到 x = 10）

我们可以从此分布中对 Y 中第一项的 X 索引进行采样（称为 x1）。然后，可以使用 P(x; (n - x1), (k - 1)) 以相同的方式对 Y 中第二个索引的分布进行采样，对于所有后续索引，依此类推。

我现在的感觉是这个问题在 O(k) 中是无法解决的，因为一般来说我们无法从常数时间内描述的分布中进行采样。如果 k = 2 那么我们可以使用二次公式在恒定时间内求解（因为概率函数简化为 0.5(x^2 + x)），但我看不到将其扩展到所有 k 的方法（我的数学是'不过还不错）。