如果你可以在原地改变序列，你可以简单地重复从0到N中抽取一个随机数，然后删除你访问过的元素，或者把它交换到最后，或者这样的方案。

从理论上讲，如果你构建了一个周期正好是 n 的随机数生成器，并且覆盖了0..n中的所有值，那么运行一次就会给予你想要的结果。
当然，这可能不是一个通用的解决方案，至少如果您正在寻找一些动态的东西，因为您必须预先创建PRNG，并且您如何做到这一点取决于n。

好好想想你如何“知道”哪些元素以前被访问过？
简短回答：你不能。（编辑好吧，除非你计算无状态伪随机生成器，但正如你自己在命令中声明的那样，这在一般情况下似乎不可行）
根据实际的序列，它可能是可行的，然而，'标记'元素为 visitedin-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--;
    }
}

与大多数算法问题一样，存在时间-空间权衡;这可以在O（1）空间中解决，如果你愿意使用O（n^2）时间来生成所有的排列。除了几个临时变量之外，这需要的唯一存储是随机数种子本身（或者，在这种情况下，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生成1000个长度为3的完整排列; ./test 10 1000000 0 5生成长度为一百万的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个数字后停止，但你必须这样做两次，首先得到结果，然后调整它。

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

我刚刚为这类事情构建了一个结构--我生成了一个堆结构（min或max，无所谓）。但是为了进行比较，我没有使用键值，而是使用随机数。插入到堆中的项因此以随机顺序放置。然后，您可以返回构成堆的基本结构的数组（将随机排序），或者您可以逐个弹出元素，然后以随机顺序返回它们。如果将这种类型的容器用作主存储（而不是将数组与堆分开），则不会产生额外的内存复杂性，因为它只是一个数组。时间复杂度为O（logN），是O（logN）的。 Shuffle 就像弹出和重新插入每个元素一样简单，O（N log N）。
我甚至构建了一个奇特的Enumerator（它是C#，但你可以用C++ Iterator做同样的事情），在你迭代到最后之后自动 Shuffle 。这意味着每次你都可以在列表中迭代多次（没有弹出），每次都得到不同的顺序，每次完整迭代后的代价是O（N log N）的 Shuffle 。（就像一副扑克牌。在每张牌都被放进弃牌堆后，你重新 Shuffle ，这样下次就不会以同样的顺序得到它们了。）

这是一个老问题，但我需要这样一个伪随机排序，答案对我来说不是很有用。
考虑两个操作：
1.你可以用一些随机掩码对“i”进行异或：j=i xor k1。它使很好的“混乱”的秩序，但可以出界。它的好处是它可以替换元素对，所以如果你最终越界了，你可以不这样做。
1.你可以将i乘以某个与n互质的常数（gcd（n，k2）= 1）模n：j=i*k2 mod n。
可以将这些组合起来，以使排序的伪随机“混乱”：

int getIndex(i) {
 if (i^k1 < n) i = i^k1;
 i = (i*k2) % n;
 if (i^k3 < n) i = i^k3;
 i = (i*k4) % n;
 return i;
}

其中k2和k4被预先计算为与n互质，并且k1和k3应该小于n。