arrays - 使用相同的模式重新排序输入，直到它变回原始顺序

Question

我找到了这个面试题，想知道有没有什么好的办法解决。我们有一个输入数组 [0, 1, 2, 3] 和一个模式数组，例如[3,1,2,0]，模式数组所做的是我们应该通过将索引为 3 的元素放在第一个位置，然后将索引为 1 的元素放在第二个位置等来重新排序输入. 所以在一次迭代后，[0, 1, 2, 3] 将变为 [3, 1, 2, 0]，在使用相同模式重新排序的另一次迭代后，它再次变为 [0, 1, 2, 3]。

问题是给定一个模式我们需要迭代多少次才能回到原来的顺序，输入数组是否有可能永远不能回到原来的顺序给定某种重新排序模式？

---

就是这个问题，我自己只知道怎么暴力破解它——不断迭代直到它和原始输入的顺序相同。关于是否可能永远回不去原来的顺序，我的做法是记录下我们目前看到的所有顺序，当我们发现一个已经访问过的顺序时，我们意识到有一个循环，我们可能永远回不去原本的。我这一段的分析可能没什么用，大家无视吧。。。

Answer 1

有一种排列符号，称为循环符号，在这种情况下可以帮助您。示例模式的循环表示法是:

(0 3) (1 2)

这意味着:位置0 的条目转到位置3。位置 3 的条目转到位置 0(只是环绕)。位置 1 的条目转到 2，2 转到 1。也可以获得更大的周期，例如:

(0 3 1) (2)

对于这种排列，结果如下所示:

      a b c d
It 1: b d c a
It 2: d a c b
It 3: a b c d

所以这个案例需要三次迭代才能恢复到原来的顺序。这个数字可以直接从循环符号中导出。在第一个示例中，有两个循环，每个循环都有两个条目。所需的总循环数是最小公倍数 lcm(2, 2) = 2。在第二个例子中，它是 lcm(3, 1) = 3。

推导循环符号并不难。您只需要迭代模式。如果您遇到还不是循环一部分的条目，请按照其路径通过模式并记住循环的长度。这将为您提供所有包含的周期的长度。最后，计算 LCM 并将其作为结果报告。