置换周期

Question

我正在研究一个有趣的置换周期问题。我们知道，任何数字排列都是由不相交的数字循环组成的。例如，假设我们的原始排列为12345。一个周期后，排列变为14235。因此1 ==> 1、2 ==> 3、3 ==> 4、4 == 2和5 ==> 5。所以我们的不相交的周期是1、234和5。假设我们像这样循环10 ^ 10次。最终结果是什么？例如，再经过一个周期，我们便达到了13425。我想尽可能有效地做到这一点。显然，由于存在模式，我们想进行模块化算术，但是如何用Java编写此代码？谢谢

Answer 1

这里的关键是对每个不相交的循环独立地使用您的模块化算术见解。

对于您的示例，您可以获得10 ^ 10个周期的结果

1. 平凡的第一个不相交周期（1）
2. 通过循环（10 ^ 10）％3 = 1次获得第二个不相交循环（234）
3. 第三个不相交循环（5）的]]

这只留下了[[查找

不连续的循环，但这不是您的问题的一部分。

Answer 2

基本上，您可以应用与有效执行功率a^n的计算时相同的策略。