14

假设您想以随机顺序迭代序列 [0 到 n],只访问每个元素一次。有没有办法在O (1) 内存中执行此操作,即无需创建 [1..n] 序列std::iota并运行它std::random_shuffle

某种以随机顺序吐出序列的迭代器将是最佳的。

一个要求是应该可以通过选择另一个种子来获得另一个随机订单。

4

6 回答 6

8

如果您可以就地改变序列,您可以简单地重复从 0-N 中抽取一个随机数,然后擦除您访问的元素,或将其交换到末尾,或类似方案。

于 2012-09-17T13:54:53.893 回答
6

理论上,如果你构建了一个周期正好为n的随机数生成器,并覆盖了 0..n 中的所有值,那么运行一次就会给你你喜欢的东西。

当然,这可能不是一个通用的解决方案,至少如果你正在寻找动态的东西,因为你必须预先创建 PRNG 并且你如何做到这一点取决于 n。

于 2012-09-17T13:46:37.003 回答
1

与大多数算法问题一样,存在时空权衡。如果您乐于使用 O(n^2) 时间来生成所有排列,这可以在 O(1) 空间中解决。除了几个临时变量之外,这需要的唯一存储是随机数种子本身(或者,在这种情况下,PRNG 对象),因为这足以重新生成伪随机数序列。

请注意,您必须在每次调用时为该函数提供相同的 PRNG,并且不能将其用于任何其他目的。

#include <random>

template<typename PRNG, typename INT>
INT random_permutation_element(INT k, INT n, PRNG prng) {
  typedef std::uniform_int_distribution<INT> dis;
  INT i = 0;
  for (; i < k; ++i) dis(0, i)(prng);
  INT result = dis(0, i)(prng);
  for (++i; i < n; ++i) if (dis(0, i)(prng) <= result) ++result;
  return result;
}

这是一个快速而肮脏的安全带。./test 1000 3生成长度为 3 的 1000 个完整排列;./test 10 1000000 0 5生成长度为 100 万的 10 个排列中的每一个的前五个元素.

#include <iostream>

int main(int argc, char** argv) {
  std::random_device rd;
  std::mt19937 seed_gen(rd());
  int count = std::stoi(argv[1]);
  int size = std::stoi(argv[2]);
  int seglow = 0;
  int seglim = size;
  if (argc > 3) seglow = std::stoi(argv[3]);
  if (argc > 4) seglim = std::stoi(argv[4]);
  while (count-- > 0) {
    std::mt19937 prng(seed_gen());
    for (int i = seglow; i < seglim; ++i)
      std::cout << random_permutation_element(i, size, prng)
                << (i < seglim - 1 ? ' ' : '\n');
  }
  return 0;
}

如果您不太可能完成任何给定的排列,则有一种更快的方法可以做到这一点,但是这种编写方式看起来更好,并且可能更容易理解。(另一种方法是以相反的顺序生成数字,这意味着您可以在生成 k 个之后停止,但您必须执行两次,首先获得结果,然后调整它。)

于 2012-09-17T20:07:36.860 回答
1

嗯……想一想。您如何“知道”以前访问过哪些元素?

简短的回答:你不能。(编辑好吧,除非您计算无状态伪随机生成器,但正如您在命令中所说的那样,这对于一般情况来说似乎不可行)

然而,根据实际序列,将元素“标记”为已访问的_in-place_可能是可行的,因此技术上需要 O(n) 存储,但算法不需要额外的存储

例子:

const int VISITED_BIT = 0x8000; // arbitrary example

bool extract(int i) { return (i & ~VISITED_BIT); }    
bool visited(int i) { return (i & VISITED_BIT); }    
bool markvisited(int& i) { i |= VISITED_BIT); }

int main()
{
    std::vector<int> v = {2,3,4,5,6};

    int remain = v.size();
    while (remain>0)
    {
        size_t idx = rand(); // or something
        if (visited(v[idx]))
            continue;

        std::cout << "processing item #" << idx << ": " << extract(v[idx]) << "\n";
        markvisited(v[idx]);
        remain--;
    }
}
于 2012-09-17T13:47:42.510 回答
0

不,没有,想想看,程序必须记住它访问过的地方。如果有一个迭代器可以随机访问它们,那么迭代器内部必须以某种方式跟踪它,而您仍然会使用内存。

于 2012-09-17T13:46:25.550 回答
0

我刚刚为这类事情构建了一个结构——我生成了一个堆结构(最小值或最大值,没关系)。但是为了比较,我没有使用键值,而是使用随机数。因此,插入堆中的项目以随机顺序放置。然后,您可以返回构成堆的基本结构的数组(将随机排序),或者您可以将元素一一弹出,然后以随机顺序取回。如果将这种类型的容器用作主存储(而不是将数组与堆分开),则不会增加内存复杂性,因为无论如何它只是一个数组。插入的时间复杂度为 O(log N),弹出顶部元素的时间复杂度为 O(log N)。洗牌就像弹出和重新插入每个元素一样简单,O(N log N)。

我什至构建了一个花哨的 Enumerator(它是 C#,但你可以使用 C++ Iterator 做同样的事情),它会在你迭代到最后时自动随机播放。这意味着每次您可以多次迭代列表(不弹出)并每次获得不同的顺序,但每次完整迭代后都会以 O(N log N) 洗牌为代价。(像一副纸牌一样思考。在每张纸牌都进入弃牌堆后,您重新洗牌,以免下一次以相同的顺序获得它们。)

于 2013-07-27T22:23:12.490 回答