algorithm - 给定一个置换函数，找出得到原始输入所需的重复次数

Question

输入:一个字符数组和一个置换函数 P。函数 P 以某种确定性方式对输入进行混洗。例如，如果 P 是(向右推)

1234 -> P -> 4123 -> P -> 3412 -> P -> 2341 -> 1234

在上面的例子中，对一个输入应用 P 四次 就会得到一个输入。P可以是恒等映射，即要求重复为一个

1234 -> P -> 1234

P 可以被视为最终打乱输入的某种映射函数，P 的输出需要是原始输入的排列。 P 可以很复杂，比如交换赔率和偶数；接下来，交换第一个和最后一个，依此类推。

你的工作是写一个函数，比方说，

public static char[] P(char[] arr) {...} # the content is unknown
public static int getNumRequired(char[] arr) {
  // your code here
}

显然，有一个蛮力解决方案——通过创建一个 while 循环，我们计算循环次数，然后在满足条件时中断循环。这里的问题是:“我们能比蛮力做得更好吗？”

有人告诉我，有一种有效的方法(或更好的方法)可以计算出获取原始输入所需的重复次数。

Answer 1

基本思路:考虑排列列表中每个数字的移动。它将形成一个特定长度的循环。每个数字组成的循环可以是0 - (n-1)范围内不同长度的循环.然后当所有循环相遇时，整个排列将重复，这将与循环长度的 LCM(最小公倍数)相同。

以算法的方式:

1. 对于每个数字，找出您得到相同数字之前的排列数。在给定的示例中，对于 1它是:1->4->3->2->1 , 所以排列数是 4 .

2. 获取上述所有排列的 LCM(最小公倍数)。这将是您寻找的号码。

在上面的例子中:

1->4->3->2->1 ==> 4
2->1->4->3->2 ==> 4
3->2->1->4->3 ==> 4
4->3->2->1->4 ==> 4
and
LCM(4, 4, 4, 4) = 4

暴力破解可能需要 O(n!)复杂。以上将最多运行 O(n)每个数字，因此整体复杂度为 O(n^2) + <complexity of getting LCM> .

注意:我相信获取两个数字的 LCM 的复杂性与获取两个数字的 GCD 的复杂性相同。一旦我弄清楚计算结果，我会更新结果。

计算 N 个数的 LCM 的复杂度:例如，我们有 4 个数字 a、b、c、d:

LCM(a, b, c, d) = a*b*c*d / GCD(abc, abd, acd, bcd)

和

GCD (abc, abd, acd, bcd) = GCD(abc, GCD(abd, GCD(acd, bcd)))

还有 GCD(x,y)可以在 O(log(x) + log(y)) 中计算时间。

在最坏的情况下，我们需要计算 LCM(1, 2, ..., n-1, n) .这将导致计算 GCD(n!/1, GCD(n!/2, GCD(n!/3, ..., GCD(n!/(n-1), n!/n)))) .这将具有 O(log(n!/1), log(n!/2) + ... + log(n!/n)) 的复杂性与 O((n-1) * log(n!)) 相同或 O(n^2 * log(n))

因此，上述方法的总体时间复杂度为 O(n^2 * log(n)) .