卡洗牌(SPOJ/Interviewstreet)

Question

之前已经问过这个问题,但是没有一个问题得到明确答复,我尝试编译我在这里找到的所有信息.如有必要,请随意合并/移动到另一个stackexchange站点.

以下是我发现的与此相关的问题:

• SPOJ:卡洗牌
• 卡洗牌[SPOJ]

该问题最初是作为Interviewstreet Code Sprint发布的,但现在它被列为实践问题.它也被移植到SPOJ.

这是问题陈述:

这是一个改组N卡的算法:

1)卡分为K等桩.

2)底部N/K卡以相同的顺序属于桩1(因此初始桩的底卡是桩1的底卡).

3)从底部开始的下一个N/K卡属于堆2,依此类推.

4)现在洗牌堆的顶牌是堆1的顶牌.下一张牌是堆2的顶牌,...,洗牌堆的Kth牌是堆K的顶牌>. (K + 1)卡是现在位于堆1顶部的卡,(K + 2)nd是现在位于堆2顶部的卡,依此类推.

例如,如果N = 6且K = 3,则在洗牌一次时牌组"ABCDEF"(从上到下)的顺序将变为"ECAFDB".

给定N和K,在将桩恢复到原始顺序之后所需的最小洗牌次数是多少？

输入:第一行包含测试用例T的数量.接下来的T行包含两个整数,每个N和K.

输出:输出T行,每个测试用例一行,包含所需的最小洗牌次数.如果牌组永远不会恢复到原始顺序,则输出-1.

约束:

• K将是N的因子.
• T <= 10000
• 2 <= K <= N <= 10 ^ 9

---

扰流警报 - 如果您想自己解决,请不要阅读下面的内容.

问题可以翻译为:

找出需要执行K-way(完美)in-shuffle以将N卡片组恢复到其初始排序的次数.

我采取了两种方法来解决这个问题.想到的第一种方法是:

• 找到一个公式,给定初始顺序中的位置将生成卡的下一个位置
• 使用公式确定每张卡从第一堆(大小为n/k)返回其初始位置所需的洗牌次数
• 返回之前确定的shuffle数的最小公倍数

该解决方案的复杂性是O(n/k + max_number_of_suhffles).这是实际的实现.这个问题是它超过了最大时间,所以我开始寻找一个允许我在接近恒定时间内得到数字的公式.

我在这里可以进行优化的最多(例如,使用一些地图在相同的排列周期中缓存计算值等)是为了让它在面试街上通过3/10测试.

---

我找到了这个实现,它假设返回到初始状态所需的shuffle数是K相对于N + 1 的乘法顺序.来自wiki:

As a consequence of Lagrange's theorem, ordn(a) always divides ?(n). 

φ(n)是Euler totient函数,ordn是组顺序 - 我们正在寻找的.我发现这篇论文使用φ来计算shuffle的数量,但它只适用于2-in-shuffle,而不是k-way.

以下是此实现的步骤:

• 预先计算了素数列表<100 000
• ?(N+1)从其主要因素计算.
• ?(N + 1)通过以各种可能的方式结合其主要因素来确定所有因素.
• 依次尝试每个因素,得到最小的因子x,进行验证k ^ x % N + 1 = 1

此实现也发布在GitHub上.

这种运行速度非常快,但自动分级器给了我10个测试中的9个"错误答案"分类,包括SPOJ和Interviewstreet.

我尝试比较两个实现的输出,但对于我输入的测试用例(已知结果和随机),这两个实现总是输出相同的东西.这很奇怪,因为我很确定第一个算法是正确的我假设第二个算法也应该是正确的.

"错误答案"分类可能来自代码中的运行时错误,但没有任何内容跳出来作为可能的原因.

我没有考虑到没有数字洗牌可以将套牌恢复到初始状态的情况 - 我的理解是这是不可能的.尽管shuffle的数量可能非常高,但有限数量的完美shuffle最终将恢复初始排序.

如果您花时间阅读本文,谢谢.:)我很好奇这个问题,我想让它解决.

Answer 1

给定 N 和 K，计算出产生的排列，并计算出它在http://en.wikipedia.org/wiki/Cycle_notation中的样子。在循环表示法中，排列是不相交循环的乘积，例如ABCDEF => ECAFDB 是(AEDFBC)，因为A->E->D->F->B->C->A。如果您的排列是这样的单个循环，则循环的长度就是您需要重复它才能回到同一位置的次数。如果排列是多个不相交循环的乘积，例如 (ABC)(DE)(F)，则需要重复的次数是各个循环长度的http://en.wikipedia.org/wiki/Least_common_multiple循环。