用次线性记忆生成排列

Question

我想知道是否有足够简单的算法来生成 N 个元素的排列，比如说1..N，它使用的O(N)内存少于内存。它不必计算第 n 个排列，但它必须能够计算所有排列。

当然，这个算法应该是某种生成器，或者使用一些O(N)内存不足的内部数据结构，因为将结果作为大小的向量返回N已经违反了对次线性内存的限制。

Answer 1

我想答案一定是“不”。

将 N 元素排列的生成器视为状态机：它必须至少包含与排列一样多的状态，否则它将在完成生成所有状态之前开始重复。

有N个！这样的排列，至少需要 ceil(log2(N!)) 位来表示。 斯特林近似告诉我们 log2(N!) 是 O(N log N)，因此我们将无法创建这样一个具有亚线性内存的生成器。