7

考虑一个问题，其中 k 个项目的随机子列表 Y 必须从 X（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) 解决方案是可以实现的。有谁知道是否是这种情况，如果是这样，边际指数的分布具有哪些属性？

4

6 回答 6

1

通过您的第一个算法，按排序顺序生成 k 个 [0, 1) 的均匀随机样本就足够了。

让 X1, ..., Xk 成为这些样本。给定 Xk = x，X1,...,Xk-1 的条件分布是 k-1 个有序的 [0, x) 的均匀随机样本，因此只需对 Xk 进行采样并递归即可。

Xk < x 的概率是多少？[0, 1)的k个独立样本中的每一个必须小于x，所以答案（Xk的累积分布函数）是x^k。要根据 cdf 进行采样，我们所要做的就是在 [0, 1): 的均匀随机样本上反转它pow(random(), 1.0 / k)。

这是我实际上会考虑实施的（预期的）O（k）算法。这个想法是将样本转储到 k 个 bin 中，对每个 bin 进行排序，然后进行连接。这是一些未经测试的 Python：

def samples(n, k):
    bins = [[] for i in range(k)]
    for i in range(k):
        x = randrange(n)
        bins[(x * k) // n].append(x)
    result = []
    for bin in bins:
        bin.sort()
        result.extend(bin)
    return result

为什么这在预期中是有效的？假设我们对每个 bin 使用插入排序（每个 bin 的预期大小为 O(1)！）。在 O(k) 的操作之上，我们将按比例支付 bin 大小的平方和的数量，这基本上是冲突的数量。由于两个样本碰撞的概率最多为 4/k，并且我们有 O(k^2) 对样本，因此预期的碰撞次数为 O(k)。

我相当强烈地怀疑 O(k) 保证可以以很高的概率做出。

于 2012-04-11T13:37:03.173 回答
1

无偏O(n+k)的解决方案是简单的高级伪代码。

  • 创建一个大小为 n 的空直方图 [初始化为所有元素为零]
  • 用范围内的 k 个均匀分布的变量填充它。（做k次histogram[inclusiveRand(1,n)]++）
  • 迭代初始列表 [A]，同时减少直方图中的元素并将元素附加到结果列表中。

解释[编辑]：

  • 这个想法是随机选择k元素n，每个元素均匀分布，并从中创建一个直方图。
  • 此直方图现在包含每个索引，结果列表中将出现i多少次。A[i]Y
  • 现在，按顺序迭代列表A，并为每个元素i插入A[i]结果Y列表histogram[i]时间。
  • 这可以保证您保持顺序，因为您按顺序插入元素，并且“永不返回”。
  • 它还保证了无偏解，因为对于每个 i,j,K: P(histogram[i]=K) = P(histogram[j]=K)，因此对于每个K，每个元素都有相同的概率出现在结果列表K时间中。

我相信可以O(k)使用订单统计信息 [X (i) ]来完成，但我无法弄清楚：\

于 2012-04-11T12:43:42.533 回答
0

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

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

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

范数 = 二项式(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 的方法（我的数学不是虽然不太好）。

于 2012-04-13T09:35:40.783 回答
0

原始列表 X 有 n 个项目。有 2**n 个可能的子列表，因为每个项目都会或不会出现在结果子列表中：每个项目都会在可能的子列表的枚举中添加一个位。您可以查看此 n 位位字的枚举。

由于您只想要具有 k 个项目的子列表，因此您对设置了 k 位的位字感兴趣。

一个实用的算法可以从 X 中选择（或不选择）第一个元素，然后考虑到所选择项目的累积数量，然后递归到 X 的最右边的 n-1 个子字符串。由于 X 列表按顺序处理，Y 列表也将按顺序处理。

于 2012-04-13T10:44:05.293 回答
0

您可以使用计数排序对 Y 进行排序，从而使排序相对于 k 呈线性。但是，为此，您需要一个额外的长度为 n 的数组。如果我们假设您已经分配了它，您可以执行您要求的代码任意多次，复杂度为 O(k)。

这个想法就像你描述的那样，但是我将使用一个大小为 n 的数组 cnt ，我假设它被初始化为 0，另一个我假设为空的“堆栈” st 。

for i = 1 to k
    A[i] = floor(rand * n) + 1
    cnt[A[i]]+=1
    if cnt[A[i]] == 1  // Needed to be able to traverse the inserted elements faster
      st.push(A[i])

for elem in st
  for i = 0 to cnt[elem]
    Y.add(X[elem])

for elem in st
  cnt[elem] = 0

编辑：正如老男孩所说，我在帖子中所说的不是真的 - 我仍然需要对 st 进行排序，这可能比原来的提议要好一些，但不会太多。所以这种方法只有在 k 与 n 相当的情况下才有效，然后我们只需线性迭代 cnt 并以这种方式构造 Y。这种方式 st 不需要：

for i = 1 to k
    A[i] = floor(rand * n) + 1
    cnt[A[i]]+=1

for i = 1 to k
  for j = 0 to cnt[i]
    Y.add(X[i])
  cnt[i] =0
于 2012-04-11T12:48:15.613 回答
0

原始列表 X 有 n 个项目。有 2**n 个可能的子列表，因为每个项目都会或不会出现在子列表中：每个项目都会在可能的子列表的枚举中添加一个位。您可以查看此 n 位位字的枚举。

由于您只想要具有 k 个项目的子列表，因此您对设置了 k 位的位字感兴趣。一个实用的算法可以从 X 中挑选（或不挑选）第一个元素，然后考虑到所选项目的累积数量，然后递归到 X 的最右边的 n-1 个子串。由于 X 列表按顺序处理，Y 列表也将按顺序处理。

#include <stdio.h>
#include <string.h>

unsigned pick_k_from_n(char target[], char src[], unsigned k, unsigned n, unsigned done);
unsigned pick_k_from_n(char target[], char src[]
                , unsigned k, unsigned n, unsigned done)
{
unsigned count=0;

if (k>n) return 0;

if (k==0) {
        target[done] = 0;
        puts(target);
        return 1;
        }
if (n > 0) {
        count += pick_k_from_n(target, src+1, k, n-1, done);

        target[done] = *src;
        count += pick_k_from_n(target, src+1, k-1, n-1, done+1);
        }

return count;
}

int main(int argc, char **argv) {

char result[20];
char *domain = "OmgWtf!";
unsigned cnt ,len, want;
want = 3;

switch (argc) {
default:
case 3:
        domain = argv[2];
case 2:
        sscanf(argv[1], "%u", &want);
case 1:
        break;
        }
len = strlen(domain);

cnt = pick_k_from_n(result, domain, want, len, 0);

fprintf(stderr, "Count=%u\n", cnt);

return 0;
}

删除递归留给读者作为练习。一些输出：

plasser@pisbak:~/hiero/src$ ./a.out 3 ABBA
BBA
ABA
ABA
ABB
Count=4
plasser@pisbak:~/hiero/src$
于 2012-04-13T11:15:47.983 回答