将随机索引挑选到已排序的数组中

Question

假设我有一个排序的值数组:

int n=4; // always lower or equal than number of unique values in array
int i[256] = {};
int v = {1 1 2 4 5 5 5 5 5 7 7 9 9 11 11 13}
// EX 1        ^         ^       ^       ^
// EX 2    ^                 ^         ^ ^
// EX 3    ^ ^           ^               ^

我想生成n个随机索引值i[0] ... i[n-1],以便:

1. v[i[0]] ... v[i[n-1]]指向一个唯一的数字(即不得指向5两次)
2. 每个数字必须是同类中最右边的(即必须指向最后 5个)
3. 应始终包括最终数字的索引(在这种情况下为13).

到目前为止我尝试过的:

1. 获取索引到最后一个唯一值
2. 洗牌索引
3. 挑出n个第一个索引

我在C中实现这一点,因此我可以依赖的标准C函数越多,代码越短越好.(例如,shuffle不是标准的C函数,但如果必须,我必须.)

Answer 1

创建最后一个索引值的数组

int last[] = { 1, 2, 3, 8, 10, 12, 14 };

Fisher-Yates将阵列洗牌.

n-1从洗牌数组中取出第一个元素.

将索引添加到最终编号.

如果需要,对结果数组进行排序.

Answer 2

该算法称为储层采样,只要您知道需要多大的样本,就可以使用该算法,但不能使用您采样的元素数量.(这个名称来源于你总是保持一个正确数量的样本的储存器.当一个新值进入时,你将它混合到储存器中,移除一个随机元素,然后继续.)

1. 创建sample大小的返回值数组n.
2. 开始扫描输入数组.每次找到新值时,将其索引添加到结尾sample,直到您有n采样元素.

3. 继续扫描数组,但现在找到新值时:

   一个.选择r[0,i]范围内的随机数,其中i是到目前为止看到的唯一值的数量.

   湾 如果r小于n,则r用新元素覆盖元素.

4. 当你到达最后,排序sample,假设你需要对它进行排序.

要确保始终拥有样本中的最后一个元素,请运行上述算法以选择大小样本n-1.只有在找到更大的元素时才考虑新元素.

该算法的大小是线性的v(加上n log n最后一步中排序的术语.)如果您已经拥有每个值的最后索引列表,则会有更快的算法(但之后您会知道宇宙的大小你开始采样了;如果你不知道,那么水库采样主要是有用的.)

事实上,它在概念上与收集所有指数然后找到Fisher-Yates shuffle的前缀没有区别.但它使用O(n)临时内存而不是足以存储整个索引列表,这可能被认为是一个加号.

这是一个未经测试的示例C实现(需要您编写该函数randrange()):

/* Produces (in `out`) a uniformly distributed sample of maximum size
 * `outlen` of the indices of the last occurrences of each unique
 * element in `in` with the requirement that the last element must
 * be in the sample.
 * Requires: `in` must be sorted.
 * Returns: the size of the generated sample, while will be `outlen` 
 *          unless there were not enough unique elements.
 * Note: `out` is not sorted, except that the last element in the
 *       generated sample is the last valid index in `in`
 */
size_t sample(int* in, size_t inlen, size_t* out, size_t outlen) {
  size_t found = 0;
  if (inlen && outlen) {
    // The last output is fixed so we need outlen-1 random indices
    --outlen; 
    int prev = in[0];
    for (size_t curr = 1; curr < inlen; ++curr) {
      if (in[curr] == prev) continue;
      // Add curr - 1 to the output
      size_t r = randrange(0, ++found);
      if (r < outlen) out[r] = curr - 1;
      prev = in[curr];
    }
    // Add the last index to the output
    if (found > outlen) found = outlen;
    out[found] = inlen - 1;
  }
  return found;
}