相关疑难解决方法(0)

我有一个不寻常的问题,可能会或可能不会被问过(虽然我没有找到任何东西,但我可能只是寻找错误的流行语).

我的任务很简单:给出自然数字的"列表",直到N [0,1,2,... N - 1]我想要改变这个序列.例如,当我输入数字4时,一个可能的结果将是[3,0,1,2].随机性应该由一些种子确定(然而这对于大多数普通语言的PRNG来说是标准的).

天真的方法是实例化一个大小为N的数组,用数字填充它并使用任何改组算法.

然而问题是,这种方法的存储器复杂性是O(n),在我的特殊情况下是不易处理的.我的想法是,编写一个生成器,迭代地在结果列表中提供数字.

更确切地说,我想要一些以迭代方式提供数字的"算法".更确切地说,概念类看起来像这样:

class Generator {
   // some state
   int nextNumber(...) {
      // some magic
   }
}

并且迭代地调用nextNumber方法提供序列的编号(即[0,1,... N-1]的任何排列.当然,这个生成器实例的状态应该比O(n)具有更好的内存复杂性再一次(我什么也得不到).

有什么算法要做,我想要什么？

我正在处理大量的整数排列.每个排列中的元素数量为K.元素大小为1个字节.我需要生成N个唯一的随机排列.
约束:K <= 144,N <= 1,000,000.

我想出了以下简单的算法:

1. 生成N个随机排列的列表.将所有排列存储在RAM中.
2. 对列表进行排序并删除所有重复项(如果有).重复数量相对较少.
3. 如果有任何重复项,请将随机排列添加到列表中,直到有N个排列并返回到步骤2.

有一个更好的方法吗？特别是,有没有办法不将所有排列存储在RAM中(在生成时将它们写在磁盘上)？

编辑:最后,需要按顺序访问生成的排列(逐个访问,不需要随机访问).RAM是更关键的因素(我宁愿不在RAM中同时存储所有排列).