algorithm - 除了 Fisher-Yates 和找到 "next permutation?"之外还存在哪些改组算法

Question

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

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

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

维基百科 lists two ，我想知道是否还有更多(除了 bogo :P 之外)

Answer 1

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 具有相同的形式，但用映射的下一步替换了对随机的调用。如果映射实际上是双射(我正在努力证明)，那么这是比 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 通过将 b 取 a 来对 S 进行操作, a 到 c, c 到 d 和 d 到 b。如果 q 是另一个排列，假设 (d b c a) 那么 pq 是通过首先应用 q 然后 p 给出 (d a b)(c)。例如，q 将 d 转换为 b，p 将 b 转换为 a，因此 pq 将 d 转换为 a。您会看到 pq 有两个循环，因为它需要 b 到 d 并修复 c。通常省略 1 周期，但为了清楚起见，我将其保留。

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

1. 不相交的周期通勤。 (a b)(c d) 等同于 (c d)(a b)
2. 我们可以按任何循环顺序排列循环中的元素。即 (a b c) = (b c a) = (c a b)

因此，给定一个排列，对循环进行排序，使最大的循环排在第一位。当两个循环的长度相同时，排列它们的项目，使最大的(我们总是可以排序一个可数集，即使是任意的)项目排在第一位。然后我们首先按照循环的长度，然后是它们的内容进行字典顺序排序。这是有序的，因为由相同循环组成的两个排列必须是相同的排列，所以如果 p > q 和 q > p 那么 p = q.

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