8

循环领导迭代算法是一种通过将所有偶数条目移动到前面并将所有奇数条目移动到后面同时保留它们的相对顺序来对数组进行洗牌的算法。例如，给定这个输入：

a 1 b 2 c 3 d 4 e 5

输出将是

a b c d e 1 2 3 4 5

该算法在 O(n) 时间内运行并且仅使用 O(1) 空间。

该算法的一个不寻常的细节是它通过将数组拆分为大小为 3 k +1 的块来工作。显然这对于​​算法正常工作至关重要，但我不知道为什么会这样。

为什么算法中需要选择 3 k + 1？

谢谢！

4

2 回答 2

11

这将是一个很长的答案。您的问题的答案并不简单，需要一些数论才能完全回答。我花了大约半天的时间研究算法，现在我有了一个很好的答案，但我不确定我能否简洁地描述它。

简短版本：

  • 将输入分成大小为 3 k + 1 的块基本上将输入分成大小为 3 k - 1 的块，由两个最终不会移动的元素包围。

  • 块中剩余的 3 k - 1 个元素根据一个有趣的模式移动：每个元素移动到通过将索引除以两个模 3 k给出的位置。

  • 这种特殊的运动模式与数论和群论中称为原根的概念相关联。

  • 因为数字 2 是一个以 3 k为模的原始根，所以从数字 1、3、9、27 等开始，并且运行该模式可以保证恰好循环遍历数组的所有元素一次并将它们放入正确的位置.

  • 这种模式高度依赖于这样一个事实，即 2 是任何 k ≥ 1 的 3 k的原始根。将数组的大小更改为另一个值几乎肯定会破坏这一点，因为保留了错误的属性。

长版

为了给出这个答案，我将分步进行。首先，我将介绍循环分解作为一种算法的动机，该算法将以正确的顺序有效地打乱元素，但有一个重要的警告。接下来，我将指出一个有趣的属性，即当您应用此排列时元素如何在数组中移动。然后，我将把它与一个称为原始根的数论概念联系起来，以解释正确实现该算法所涉及的挑战。最后，我将解释为什么这会导致选择 3 k + 1 作为块大小。

循环分解

假设您有一个数组 A 和该数组元素的排列。按照标准的数学符号，我们将该数组的排列表示为 σ(A)。我们可以将初始数组 A 排列在置换数组 σ(A) 的顶部，以了解每个元素的最终位置。例如，这是一个数组及其排列之一：

   A    0 1 2 3 4
 σ(A)   2 3 0 4 1

我们可以描述一个排列的一种方法就是列出该排列中的新元素。但是，从算法的角度来看，将排列表示为循环分解通常更有帮助，这是一种写出排列的方法，通过展示如何从初始数组开始然后循环排列其中的一些元素来形成排列。

看看上面的排列。首先，看看 0 在哪里结束。在 σ(A) 中，元素 0 最终取代了元素 2 的位置。反过来，元素 2 最终取代了元素 0 的位置。我们用 (0 2) 来表示这一点，表示 0 应该去 2 曾经的位置，而 2 应该去 0 曾经的地方。

现在，看看元素 1。元素 1 最终出现在 4 的位置。然后数字 4 结束于 3 的位置，元素 3 结束于 1 的位置。我们通过写作 (1 4 3) 来表示这一点，即 1 应该去往 4 的位置， 4 应该去往 3 的地方， 并且 3 应该去往 1 的地方。

将这些组合在一起，我们可以将上述元素的整体排列表示为 (0 2)(1 4 3) - 我们应该交换 0 和 2，然后循环排列 1、4 和 3。如果我们从最初的数组，我们最终会得到我们想要的置换数组。

循环分解对于就地置换数组非常有用，因为它可以在 O(C) 时间和 O(1) 辅助空间中置换任何单个循环，其中 C 是循环中的元素数。例如，假设您有一个循环 (1 6 8 4 2)。您可以使用如下代码置换循环中的元素：

int[] cycle = {1, 6, 8, 4, 2};

int temp = array[cycle[0]];
for (int i = 1; i < cycle.length; i++) {
    swap(temp, array[cycle[i]]);
}
array[cycle[0]] = temp;

这可以通过交换所有东西直到一切都停止来工作。除了存储循环本身所需的空间使用外，它只需要 O(1) 辅助存储空间。

通常，如果您想设计一种算法，将特定排列应用于元素数组，通常可以使用循环分解来实现。一般算法如下：

for (each cycle in the cycle decomposition algorithm) {
   apply the above algorithm to cycle those elements;
}

该算法的整体时间和空间复杂度取决于以下因素：

  1. 我们能多快确定我们想要的循环分解？
  2. 我们如何有效地将循环分解存储在内存中？

为了得到解决手头问题的 O(n) 时间、O(1) 空间算法，我们将展示有一种方法可以确定 O(1) 时间和空间中的循环分解。由于所有内容都将仅移动一次，因此整体运行时间将为 O(n)，整体空间复杂度将为 O(1)。正如您将看到的那样，到达那里并不容易，但话又说回来，它也不可怕。

排列结构

这个问题的首要目标是获取一个包含 2n 个元素的数组并将其打乱，以便偶数位置的元素最终位于数组的前面，奇数位置的元素最终位于数组的末尾。现在假设我们有 14 个元素，如下所示：

 0  1  2  3  4  5  6  7  8  9 10 11 12 13

我们想打乱元素，使它们像这样出来：

 0  2  4  6  8 10 12  1  3  5  7  9 11 13

关于这种排列的产生方式，我们可以得到一些有用的观察。首先，请注意第一个元素在此排列中不会移动，因为偶数索引元素应该出现在数组的前面，并且它是第一个偶数索引元素。接下来，请注意最后一个元素在此排列中不会移动，因为奇数索引元素应该在数组的后面结束，并且它是最后一个奇数索引元素。

这两个观察结果放在一起意味着，如果我们想以所需的方式置换数组的元素，我们实际上只需要置换由整个数组组成的子数组，去掉第一个和最后一个元素。因此，展望未来，我们将纯粹专注于置换中间元素的问题。如果我们能解决这个问题，那么我们就解决了整个问题。

现在，让我们看看数组的中间元素。从我们上面的例子中，这意味着我们将从这样一个数组开始：

 Element    1  2  3  4  5  6  7  8  9 10 11 12
 Index      1  2  3  4  5  6  7  8  9 10 11 12

我们想让数组看起来像这样：

 Element    2  4  6  8 10 12  1  3  5  7  9 11
 Index      1  2  3  4  5  6  7  8  9 10 11 12

因为这个数组是通过取一个索引为 0 的数组并切掉第一个和最后一个元素而形成的，所以我们可以将其视为一个索引数组。这将是至关重要的，因此请务必牢记这一点。

那么我们究竟如何才能产生这种排列呢？好吧，对于初学者来说，看看每个元素并试图找出它开始和结束的地方并没有什么坏处。如果我们这样做，我们可以这样写：

  • 位置 1 的元素在位置 7 结束。
  • 位置 2 的元素最终位于位置 1。
  • 位置 3 的元素最终位于位置 8。
  • 位置 4 的元素最终位于位置 2。
  • 位置 5 的元素在位置 9 结束。
  • 位置 6 的元素最终位于位置 3。
  • 位置 7 的元素最终位于位置 10。
  • 位置 8 的元素最终位于位置 4。
  • 位置 9 的元素最终位于位置 11。
  • 位置 10 的元素最终位于位置 5。
  • 位置 11 的元素最终位于位置 12。
  • 位置 12 的元素最终位于位置 6。

如果您查看此列表，您可以发现一些模式。首先，请注意所有偶数元素的最终索引始终是该元素位置的一半。例如，位置 4 的元素结束于位置 2，位置 12 的元素结束于位置 6，等等。这是有道理的 - 我们将所有偶数元素推到数组的前面，所以一半的元素来到他们之前将被转移并移开。

现在，奇数元素呢？嗯，总共有 12 个元素。每个奇数元素都被推到后半部分，因此位置 2k+1 的奇数元素将至少被推到位置 7。它在后半部分中的位置由 k 的值给出。因此，奇数位置 2k+1 的元素被映射到位置 7+k。

我们可以花一点时间来概括这个想法。假设我们要置换的数组的长度为 2n。位置 2x 的元素将映射到位置 x（同样，偶数减半），位置 2x+1 的元素将映射到位置 n + 1 + x。重申这一点：

元素在位置 p 的最终位置确定如下：

  • 如果对于某个整数 x，p = 2x，则 2x ↦ x
  • 如果对于某个整数 x，p = 2x+1，则 2x+1 ↦ n + 1 + x

现在我们要做一些完全疯狂和意想不到的事情。现在，我们有一个分段规则来确定每个元素在哪里结束：我们要么除以 2，要么我们做一些涉及 n + 1 的奇怪事情。然而，从数论的角度来看，有一个单一的统一规则来解释哪里所有元素都应该结束。

我们需要的洞察力是，在这两种情况下，在某种程度上，我们似乎将索引除以二。在偶数情况下，新索引实际上是由仅除以 2 形成的。对于奇怪的情况，新索引看起来像是由除以 2 形成的（注意 2x+1 变为 x + (n + 1)），但其中有一个额外的项。然而，在数论的意义上，这两者实际上都对应于除以二。这就是为什么。

与其取源索引并除以2 得到目标索引，不如取目标索引乘以2 会怎样？如果我们这样做，就会出现一个有趣的模式。

假设我们的原始数字是 2x。然后目标是 x，如果我们将目标索引加倍以返回 2x，我们最终得到源索引。

现在假设我们的原始数字是 2x+1。然后目的地是n + 1 + x。现在，如果我们将目标索引加倍会发生什么？如果我们这样做，我们会得到 2n + 2 + 2x。如果我们重新排列它，我们也可以将它重写为 (2x+1) + (2n+1)。换句话说，我们已经取回了原始索引，加上一个额外的 (2n+1) 项。

现在是踢球者：如果我们所有的算术都是模 2n + 1 完成的呢？在这种情况下，如果我们的原始数字是 2x + 1，那么目标索引的两倍是 (2x+1) + (2n+1) = 2x + 1（模 2n+1）。换句话说，目标索引确实是源索引的一半，只是对 2n+1 取模！

这使我们得到了一个非常非常有趣的见解：2n 元素数组中每个元素的最终目的地是通过将该数字除以 2 给出的，模 2n+1。这意味着确实有一个很好的统一规则来确定一切的去向。我们只需要能够除以两个模 2n+1。恰好在偶数情况下，这是正常的整数除法，而在奇数情况下，它可以采用 n + 1 + x 的形式。

因此，我们可以用以下方式重构我们的问题：给定一个由 2n 个元素组成的索引为 1 的数组，我们如何置换这些元素，以使最初位于索引 x 的每个元素最终都位于位置 x/2 mod (2n+1 )?

重新审视循环分解

在这一点上，我们已经取得了很大的进步。给定任何元素，我们知道该元素应该在哪里结束。如果我们能找到一种很好的方法来对整个排列进行循环分解，那么我们就完成了。

不幸的是，这就是事情变得复杂的地方。例如，假设我们的数组有 10 个元素。在这种情况下，我们希望像这样转换数组：

 Initial:  1  2  3  4  5  6  7  8  9 10
 Final:    2  4  6  8 10  1  3  5  7  9

该排列的循环分解为 (1 6 3 7 9 10 5 8 4 2)。如果我们的数组有 12 个元素，我们想像这样转换它：

 Initial:  1  2  3  4  5  6  7  8  9 10 11 12
 Final:    2  4  6  8 10 12  1  3  5  7  9 11

这具有循环分解（1 7 10 5 9 11 12 6 3 8 4 2 1）。如果我们的数组有 14 个元素，我们想像这样转换它：

 Initial:  1  2  3  4  5  6  7  8  9 10 11 12 13 14
 Final:    2  4  6  8 10 12 14  1  3  5  7  9 11 13

这具有循环分解 (1 8 4 2)(3 9 12 6)(5 10)(7 11 13 14)。如果我们的数组有 16 个元素，我们想像这样转换它：

 Initial:  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
 Final:    2  4  6  8 10 12 14 16  1  3  5  7  9 11 13 15

这具有循环分解（1 9 13 15 16 8 4 2）（3 10 5 11 14 7 12 6）。

这里的问题是这些周期似乎没有遵循任何可预测的模式。如果我们要尝试在 O(1) 空间和 O(n) 时间内解决这个问题，这将是一个真正的问题。即使给定任何单个元素，我们可以找出哪个循环包含它并且我们可以有效地打乱该循环，但不清楚我们如何确定哪些元素属于哪些循环，有多少不同的循环等等。

原始根

这就是数论的用武之地。请记住，每个元素的新位置是通过将该数字除以 2 形成的，模 2n+1。反过来想，我们可以通过乘以两个模 2n+1来计算出哪个数字将代替每个数字。因此，我们可以通过反向循环分解来思考这个问题：我们选择一个数字，继续将它乘以 2 并修改 2n+1，然后重复直到完成循环。

这就产生了一个经过充分研究的问题。假设我们从数字 k 开始，考虑序列 k、2k、2 2 k、2 3 k、2 4 k 等，都以 2n+1 为模。这样做会根据您正在修改的奇数 2n+1 给出不同的模式。这就解释了为什么上述循环模式似乎有些武断。

我不知道有人是怎么想出来的，但事实证明，数论有一个很好的结果，它讨论了如果你将这个模式 mod 3 k用于某个数字 k 会发生什么：

定理：考虑序列 3 s , 3 s ·2 , 3 s ·2 2 , 3 s ·2 3 , 3 s ·2 4等。对于某些 k ≥ s ，所有模 3 k 。这个序列循环遍历 1 和 3 k之间的每个数字，包括在内，可以被 3 s整除但不能被 3 s+1整除。

我们可以通过几个例子来试试这个。让我们对 27 = 3 2取模。该定理说，如果我们查看 3、3·2、3·4 等，所有这些都以 27 为模，那么我们应该看到所有小于 27 且能被 3 整除且不能被 9 整除的数。好吧，让我们看看我们得到什么：

  • 3 · 2 0 = 3 · 1 = 3 = 3 mod 27
  • 3 · 2 1 = 3 · 2 = 6 = 6 mod 27
  • 3 · 2 2 = 3 · 4 = 12 = 12 mod 27
  • 3 · 2 3 = 3 · 8 = 24 = 24 mod 27
  • 3 · 2 4 = 3 · 16 = 48 = 21 mod 27
  • 3 · 2 5 = 3 · 32 = 96 = 15 mod 27
  • 3 · 2 6 = 3 · 64 = 192 = 3 mod 27

我们最终看到了 3、6、12、15、21 和 24（尽管不是按照那个顺序），它们确实是所有小于 27 的可以被 3 整除但不能被 9 整除的数字。

我们也可以尝试这个工作 mod 27 并考虑 1, 2, 2 2 , 2 3 , 2 4 mod 27，我们应该看到所有小于 27 的数字都可以被 1 整除且不能被 3 整除。换句话说，这应该返回所有小于 27 且不能被 3 整除的数字。让我们看看这是不是真的：

  • 2 0 = 1 = 1 模 27
  • 2 1 = 2 = 2 模 27
  • 2 2 = 4 = 4 模 27
  • 2 3 = 8 = 8 模 27
  • 2 4 = 16 = 16 模 27
  • 2 5 = 32 = 5 模 27
  • 2 6 = 64 = 10 模 27
  • 2 7 = 128 = 20 模 27
  • 2 8 = 256 = 13 模 27
  • 2 9 = 512 = 26 模 27
  • 2 10 = 1024 = 25 模 27
  • 2 11 = 2048 = 23 模 27
  • 2 12 = 4096 = 19 模 27
  • 2 13 = 8192 = 11 模 27
  • 2 14 = 16384 = 22 模 27
  • 2 15 = 32768 = 17 模 27
  • 2 16 = 65536 = 7 模 27
  • 2 17 = 131072 = 14 模 27
  • 2 18 = 262144 = 1 模 27

对这些进行排序，我们得到了数字 1、2、4、5、7、8、10、11、13、14、16、17、19、20、22、23、25、26（尽管不是按这个顺序） . 这些正是1 到 26 之间的数字，不是三的倍数！

这个定理对算法至关重要，原因如下：如果 2n+1 = 3 k对于某个数字 k，那么如果我们处理包含 1 的循环，它将正确地打乱所有不是三的倍数的数字。如果我们然后从 3 开始循环，它将正确地打乱所有能被 3 整除但不能被 9 整除的数字。如果我们然后从 9 开始循环，它将正确地打乱所有能被 9 整除但不能被 27 整除的数字。更一般地，如果我们对数字 1、3、9、27、81 等使用循环 shuffle 算法，那么我们将正确地重新定位数组中的所有元素，而不必担心我们错过任何东西。

那么这如何连接到 3 k + 1 呢？好吧，我们需要有 2n + 1 = 3 k，所以我们需要有 2n = 3 k - 1。但是请记住 - 当我们这样做时，我们删除了数组的第一个和最后一个元素！将它们添加回来告诉我们，我们需要大小为3 k + 1的块才能使此过程正常工作。如果块是这个大小，那么我们肯定知道循环分解将由一个包含 1 的循环、一个包含 3 的非重叠循环、一个包含 9 的非重叠循环等组成，并且这些循环将包含数组的所有元素. 因此，我们可以开始循环 1、3、9、27 等，并且绝对有保证一切都得到正确洗牌。太棒了！

为什么这个定理是正确的？事实证明，一个数字 k ，其中 1、k、k 2、k 3等 mod p n循环遍历所有不是 p 的倍数的数字（假设 p 是素数）称为编号 p n。有一个定理说 2 是所有数字 k 的 3 k的原始根，这就是这个技巧有效的原因。如果我有时间，我想回来编辑这个答案以包含这个结果的证明，但不幸的是，我的数论还没有达到我知道如何做到这一点的水平。

概括

这个问题很有趣。它涉及除以两个模奇数、循环分解、原始根和三的幂的可爱技巧。我感谢这篇 arXiv 论文，该论文描述了一个类似（尽管完全不同）的算法，并让我了解了该技术背后的关键技巧，然后让我为你描述的算法制定了细节。

希望这可以帮助！

于 2015-07-02T19:35:54.387 回答
3

这是 templatetypedef 的答案中缺少的大部分数学论点。（其余的比较无聊。）

引理：对于所有整数k >= 1，我们有 2^(2*3^(k-1)) = 1 + 3^k mod 3^(k+1)。

证明：通过对 的归纳k。

基本情况 ( k = 1)：我们有2^(2*3^(1-1)) = 4 = 1 + 3^1 mod 3^(1+1).

归纳案例 ( k >= 2)：如果2^(2*3^(k-2)) = 1 + 3^(k-1) mod 3^k，则q = (2^(2*3^(k-2)) - (1 + 3^(k-1)))/3^k。

 2^(2*3^(k-1)) = (2^(2*3^(k-2)))^3
               = (1 + 3^(k-1) + 3^k*q)^3
               = 1 + 3*(3^(k-1)) + 3*(3^(k-1))^2 + (3^(k-1))^3
                   + 3*(1+3^(k-1))^2*(3^k*q) + 3*(1+3^(k-1))*(3^k*q)^2 + (3^k*q)^3
               = 1 + 3^k mod 3^(k+1).

定理：对于所有整数i >= 0和k >= 1，我们有 2^i = 1 mod 3^k当且仅当i = 0 mod 2*3^(k-1)。

证明：“如果”方向来自引理。如果 i = 0 mod 2*3^(k-1)，那么

2^i = (2^(2*3^(k-1)))^(i/(2*3^(k-1)))
    = (1+3^k)^(i/(2*3^(k-1))) mod 3^(k+1)
    = 1 mod 3^k.

“仅当”方向是通过对 进行归纳k。

基本情况 ( k = 1): if i != 0 mod 2, then i = 1 mod 2, and

2^i = (2^2)^((i-1)/2)*2
    = 4^((i-1)/2)*2
    = 2 mod 3
    != 1 mod 3.

归纳案例 ( k >= 2)：如果2^i = 1 mod 3^k，则 2^i = 1 mod 3^(k-1)，并且归纳假设暗示 i = 0 mod 2*3^(k-2)。让j = i/(2*3^(k-2)). 根据引理，

1 = 2^i mod 3^k
  = (1+3^(k-1))^j mod 3^k
  = 1 + j*3^(k-1) mod 3^k,

其中删除的项可被(3^(k-1))^2、 so j = 0 mod 3和整除i = 0 mod 2*3^(k-1)。

于 2015-07-03T01:34:05.233 回答