4

特别是在同一类型的一维项目集的域中，例如整数向量。

例如，假设您有一个大小为 32,768 的向量，其中包含从 0 到 32,767 的排序整数。

我所说的“下一个排列”的意思是在词汇排序系统中执行下一个排列。

维基百科列出了两个，我想知道是否还有更多（除了一些 bogo :P）

4

5 回答 5

7

O(N) 实现 这是基于 Eyal Schneider 的映射 Zn！-> P(n)

def get_permutation(k, lst):
    N = len(lst)
    while N:
        next_item = k/f(N-1)
        lst[N-1], lst[next_item] = lst[next_item], lst[N-1]
        k = k - next_item*f(N-1)
        N = N-1
    return lst

它通过将转换步骤与寻找排列相结合来减少他的 O(N^2) 算法。它本质上与 Fisher-Yates 具有相同的形式，但用映射的下一步替换了对 random 的调用。如果映射实际上是双射（我正在努力证明），那么这是一个比 Fisher-Yates 更好的算法，因为它只调用一次伪随机数生成器，因此效率更高。还要注意，这会返回置换 (N! - k) 而不是置换 k 的作用，但这没有什么影响，因为如果 k 在 [0, N!] 上是一致的，那么 N! -k。

旧答案

这与“下一个”排列的想法略有关系。如果项目可以很好地排序，那么可以在排列上构建字典顺序。这允许您从整数构造一个映射到排列空间。

那么找一个随机排列就相当于在0到N之间选择一个随机整数！并构造相应的排列。该算法将与计算所讨论的集合的第 n 个排列一样有效（并且难以实现）。如果我们对 n 的选择是一致的，这很容易给出一个一致的排列选择。

关于排序排列的更多细节。给定一个集合S = {a b c d}，数学家将 的排列集合S视为一个具有组合运算的群。如果p是一个排列，假设(b a c d)，然后p通过S将 b 到 a、a 到 c、c 到 d 和 d 到 b 来进行操作。ifq是另一种排列，可以说(d b c a)thenpq是通过首先应用q然后p给出(d a b)(c). 例如，q将 d 带到 b 并将pb 带到 a 以便pq将 d 带到 a。你会看到它pq有两个周期，因为它需要 b 到 d 并修复 c。习惯上省略 1-cycles，但为了清楚起见，我将其保留。

我们将使用群论中的一些事实。

  1. 不相交的循环通勤。(a b)(c d)是相同的(c d)(a b)
  2. 我们可以以任何循环顺序将元素排列在一个循环中。那是(a b c) = (b c a) = (c a b)

因此，给定一个排列，对循环进行排序，以便最大的循环首先出现。当两个循环的长度相同时，排列它们的项目，以便最大的（我们总是可以订购一个可数集，即使是任意的）项目在前。然后，我们首先对循环的长度进行字典排序，然后对它们的内容进行排序。这是有序的，因为由相同循环组成的两个排列必须是相同的排列，所以 ifp > q和q > pthen p = q。

该算法可以在 O(N!logN! + N!) 时间内轻松执行。只需构建所有排列（编辑：为了清楚起见，当我提出这个建议时，我戴着我的数学家帽子，无论如何它都是在开玩笑），快速排序并找到第 n 个。不过，它与您提到的两种算法不同。

于 2010-08-30T10:46:57.467 回答
5

这是一个关于如何改进aaronasterling答案的想法。它避免生成所有 N! 排列并根据它们的字典顺序对它们进行排序，因此具有更好的时间复杂度。

在内部，它使用了一种不寻常的排列表示，它模拟了从缩小数组中选择和删除的过程。例如，序列 <0,1,0> 表示从 [0,1,2] 中删除项目 #0，然后从 [1,2] 中删除项目 #1，然后从 [ 中删除项目 #0 得到的排列。 1]。得到的排列是 <0,2,1>。使用这种表示，第一个排列将始终为 <0,0,...0>，最后一个排列将始终为 <N-1,N-2,...0>。我将这种特殊表示称为“数组表示”。

显然，通过使用数组并在必要时缩小它，可以在 O(N^2) 时间内将大小为 N 的数组表示转换为标准排列表示。

以下函数可用于返回数组表示中 {0,1,2...,N-1} 上的第 K 个排列：

getPermutation(k, N) {
    while(N > 0) {
        nextItem = floor(k / (N-1)!)
        output nextItem
        k = k - nextItem * (N-1)!
        N = N - 1
    }
}

该算法在 O(N^2) 时间内工作（由于表示转换），而不是 O(N!log N) 时间。

- 例子 -

getPermutation(4,3) 返回 <2,0,0>。这个数组表示对应于 <C,A,B>，它实际上是 {A,B,C} 上排列的有序列表中索引 4 处的排列：

ABC
ACB
BAC
BCA
CAB
CBA
于 2010-08-31T22:16:38.207 回答
3

您可以调整合并排序，使其随机打乱输入而不是对其进行排序。

特别是，在合并两个列表时，您随机选择新的头元素，而不是选择它作为最小的头元素。从第一个列表中选择元素的概率必须是第一个列表n/(n+m)的n长度和m第二个列表的长度，这样才能正常工作。

我在这里写了一个详细的解释：Random Permutations and Sorting。

于 2010-08-30T09:54:57.567 回答
2

另一种可能性是构建一个周期等于您想要的项目数的 LFSR 或 PRNG。

于 2010-08-29T17:57:56.067 回答
0

从排序数组开始。选择 2 个随机索引，在这些索引处切换元素。重复 O(n lg n) 次。

您需要重复 O(n lg n) 次以确保分布接近均匀。（您需要确保每个索引至少被挑选一次，这是一个垃圾箱问题。）

于 2010-08-29T18:08:21.337 回答