5

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

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

4

5 回答 5

1

让我们假设随机排列一次生成一个条目。生成器的状态必须对剩余的元素集进行编码（运行到完成），因此，由于不能排除任何可能性，因此生成器状态至少为 n 位。

于 2011-11-07T23:53:59.157 回答
0

我认为即使存储您的结果（这将是 N 个项目的有序列表）在内存中也将是 O(N)，不是吗？

无论如何，为了回答您稍后关于随机选择排列的问题，这里有一种比只产生所有 N 更好的技术！例如，列表中的可能性，然后随机选择一个索引。如果我们可以随机选择索引并从中生成相关的排列，我们会好得多。

我们可以想象您的单词/排列的字典顺序，并根据单词/排列在字典中的出现顺序将唯一编号与这些相关联。例如，三个字符上的单词将是

   perm.              index
    012    <---->       0
    021    <---->       1
    102    <---->       2
    120    <---->       3
    201    <---->       4
    210    <---->       5

稍后您会看到为什么使用我们所做的数字最容易，但其他数字可以通过更多的工作来适应。

要随机选择一个，您可以从 0 ... N!-1 范围内以均匀的概率随机选择其相关索引（我知道，即使是中等大的 N，最简单的实现显然也是不可能的，但是我认为有不错的解决方法），然后确定其相关的排列。请注意，列表以最后 N-1 个元素的所有排列开始，保持第一个数字固定等于 0。在这些可能性用尽之后，我们生成所有以 1 开头的那些。在这些之后（N-1）！排列已用尽，我们生成以 2 开头的排列。等等。因此我们可以确定前导数字是 Floor[R / (N-1)!]，其中 R 是上面所示意义上的索引。现在看看为什么我们也将索引归零？

为了生成排列中剩余的 N-1 位，假设我们确定了 Floor[R/(N-1)!] = a0。从列表 {0, ..., N-1} - {a0} 开始（设置减法）。我们想要这个列表的第 Q 个排列，因为 Q = R mod (N-1)!。除了考虑到缺少数字这一事实外，这与我们刚刚解决的问题相同。递归。

于 2011-11-08T04:12:51.017 回答
0

也许你可以，用阶乘数。您可以逐步从中提取结果排列，因此您不必将整个结果保存在内存中。

但我可能开始的原因是，我不确定阶数本身大小的增长行为是什么。如果它适合一个 32 位整数或类似的东西，N 将被限制为一个常数，所以 O(N) 将等于 O(1)，所以我们必须为它使用一个数组，但我不确定它会有多大以 N 表示。

于 2011-11-08T08:34:11.180 回答
0

我认为答案必须是“不”。

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

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

于 2011-11-07T23:53:42.810 回答
0

C++ 算法next_permutation对序列进行就地重排，使其进入下一个排列，或者false在不存在进一步排列时返回。算法如下：

template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last) {
    if (first == last) return false; // False for empty ranges.
    BidirectionalIterator i = first;
    ++i;
    if (i == last) return false; // False for single-element ranges.
    i = last;
    --i;
    for(;;) {
        BidirectionalIterator ii = i--;
        // Find an element *n < *(n + 1).
        if (*i <*ii) {
            BidirectionalIterator j = last;
            // Find the last *m >= *n.
            while (!(*i < *--j)) {}
            // Swap *n and *m, and reverse from m to the end.
            iter_swap(i, j);
            reverse(ii, last);
            return true;
        }
        // No n was found.
        if (i == first) {
            // Reverse the sequence to its original order.
            reverse(first, last);
            return false;
        }
    }
}

这对生成的每个排列使用常量空间（迭代器）。你认为是线性的吗？

于 2011-11-07T23:54:11.400 回答