java卡洗牌（SPOJ/Interviewstreet）

Question

这个问题以前有人问过，但是没有一个得到明确的回答，我尝试整理我在这里找到的所有信息。如有必要，请随时合并/移动到其他stackexchange站点

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

• SPOJ:Card Shuffling
• Card Shuffling [SPOJ]

这个问题最初是作为Interviewstreet代码Sprint发布的，但现在它被列为a practice problem。这也是ported to SPOJ

以下是问题陈述：

Here is an algorithm for shuffling N cards:

1) The cards are divided into K equal piles.

2) The bottom N / K cards belong to pile 1 in the same order (so the bottom card of the initial pile is the bottom card of pile 1).

3) The next N / K cards from the bottom belong to pile 2, and so on.

4) Now the top card of the shuffled pile is the top card of pile 1. The next card is the top card of pile 2, ..., the Kth card of the shuffled pile is the top > card of pile K. Then (K + 1)th card is the card which is now at the top of pile 1, the (K + 2)nd is the card which is now at the top of pile 2 and so on.

For example, if N = 6 and K = 3, the order of a deck of cards "ABCDEF" (top to bottom) when shuffled once would change to "ECAFDB".

Given N and K, what is the least number of shuffles needed after which the pile is restored to its original order?

Input: The first line contains the number of test cases T. The next T lines contain two integers each N and K.

Output: Output T lines, one for each test case containing the minimum number of shuffles needed. If the deck never comes back to its original order, output -1.

Constraints:

• K will be a factor of N.
• T <= 10000
• 2 <= K <= N <= 10^9

---

扰流板警报-如果你想自己解决问题，请不要阅读下面的内容

问题可以解释为：

Find the number of times a K-way (perfect) in-shuffle needs to be performed to restore a deck of N cards to its initial ordering.

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

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

该解的复杂度为O（n/k+suhffles的最大个数）Here's the actual implementation。问题是它超过了最长时间，所以我开始寻找一个公式，可以让我在几乎恒定的时间内得到这个数字

我在这里能优化的最多（例如，在相同的排列周期中使用一些映射缓存计算值等）是使其通过interviewstreet上的3/10测试

---

我找到了this implementation，它假设返回初始状态所需的随机数是K相对于N+1的multiplicative order。从wiki：

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

φ（n）是Euler totient function，ordn是group order-我们正在寻找的。我发现this paper使用φ来计算洗牌次数，但它只适用于洗牌中的2路，而不是k路

以下是此实施的步骤：

• 预计算素数列表<；十万
• 从其素因子计算出φ(N+1)
• 通过以所有可能的方式组合其主要因素，确定了φ(N + 1)的所有因素
• 依次尝试每个因子，并得到最小的一个x，它验证k ^ x % N + 1 = 1

这个实现也是posted on GitHub

这运行得非常快，但是自动评分器给了我一个“错误答案”分类，10个测试中有9个是在SPOJ和Interviewstreet上

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

“错误答案”分类可能来自代码中的运行时错误，但没有任何可能的原因

我没有考虑任何数字洗牌都不能使牌组返回初始状态的情况——我的理解是这是不可能的。有限数量的完美洗牌最终将恢复初始顺序，即使洗牌的数量可能非常高

如果您花时间阅读本文，谢谢。：）我对这个问题很好奇，我想把它解决掉

Answer 1

#include <iostream>
using namespace std;
int main() 
{
    int t, m , n, c, p, k, pos, cases;

    cin>>cases;

    while(cases )
    {
        cin>>t;
        cin>>k;

        p = t/k;
        pos = 1;
        c = 0;

        do
        {
            c++;
            m = (pos - 1)%p + 1;
            n = k - (pos - m)/p;
            pos = k*(m-1) + n;

        }while(pos!=1);

        cout<<c<<endl;


    }
    return 0;
}

Answer 2

给定N和K，计算出产生的置换，并计算出它在http://en.wikipedia.org/wiki/Cycle_notation中的样子。在循环表示法中，置换是不相交循环的产物，例如ABCDEF=>；ECAFDB是（AEDFBC），因为A->；E->；D->；F->；B->；C->；答：如果你的置换是这样一个周期，周期的长度就是你需要重复它回到同一个地方的次数。如果置换是多个不相交循环（如（ABC）（DE）（F）的乘积，则需要重复的次数是单个循环长度的http://en.wikipedia.org/wiki/Least_common_multiple

Answer 3

这是我在纸上做了一些观察后得出的结论

class CardShuffle {
    private long k;
    private long n;
    private long kn;
    private long kn2;

    public CardShuffle(long k, long n) {
            //I omitted some checks done here
        this.k = k;
        this.n = n;
        this.kn = k / n;
        this.kn2 = k - kn;
    }

    public long shuffle() {
        long count = 0L;
        long next = 0L;
        do {
               //this can be further optimized
           next = kn2 - kn * (next % n) + (next / n); 
           ++count;
        } while((next != 0L) && (count < k));
        if(count > k)
           return -1;
        return count;
    }
}

结果是

Testing 1000000 : 2
#ms: 3.121905
#ms: 1424.487191
#1: 9900 #2: 9900
Testing 1000000 : 5
#ms: 1.409955
#ms: 556.329366
#1: 2475 #2: 2475
Testing 1000000 : 10
#ms: 0.007823
#ms: 186.797204
#1: 12 #2: 12
Testing 1000000 : 20
#ms: 0.590298
#ms: 275.751527
#1: 4950 #2: 4950
Testing 1000000 : 25
#ms: 0.298642
#ms: 260.559372
#1: 2475 #2: 2475
Testing 1000000 : 40
#ms: 1.187581
#ms: 241.956729
#1: 9900 #2: 9900
Testing 1000000 : 50
#ms: 1.187581
#ms: 241.015548
#1: 9900 #2: 9900
Testing 9999999 : 41841
#ms: 14.499887
#ms: 1829.868042
#1: 125000 #2: 125000
Testing 9999999 : 3333333
#ms: 58.119398
#ms: 311.005728
#1: 500000 #2: 500000
Testing 9999999 : 13947
#ms: 52.704185
#ms: 2095.336418
#1: 500000 #2: 500000

根据此输入进行测试

10
1000000 2
1000000 5
1000000 10
1000000 20
1000000 25
1000000 40
1000000 50
9999999 41841
9999999 3333333
9999999 13947

第一个#ms是我的方法花费的时间（毫秒），第二个是你的。 #1和#2分别是结果

至于这个输入

15
1000000000 2
1000000000 5
1000000000 10
1000000000 20
1000000000 25
1000000000 40
1000000000 50
1000000000 1000
1000000000 200000000
1000000000 250000000
1000000000 500000000
1000000000 50000000
999999999 1001001
999999999 37037037
999999999 333333333

我的方法在中找到了解决方案

Testing 1000000000 : 2
#ms: 71.360466
#1: 525780
Testing 1000000000 : 5
#ms: 68.987259
#1: 525780
Testing 1000000000 : 10
#ms: 0.008381
#1: 18
Testing 1000000000 : 20
#ms: 75.608492
#1: 525780
Testing 1000000000 : 25
#ms: 31.843154
#1: 262890
Testing 1000000000 : 40
#ms: 33.014531
#1: 262890
Testing 1000000000 : 50
#ms: 84.27384
#1: 525780
Testing 1000000000 : 1000
#ms: 0.006705
#1: 6
Testing 1000000000 : 200000000
#ms: 53.991778
#1: 525780
Testing 1000000000 : 250000000
#ms: 43.765898
#1: 262890
Testing 1000000000 : 500000000
#ms: 54.457201
#1: 525780
Testing 1000000000 : 50000000
#ms: 68.080999
#1: 525780
Testing 999999999 : 1001001
#ms: 115.060154
#1: 1000000
Testing 999999999 : 37037037
#ms: 5783.539528
#1: 50000000
Testing 999999999 : 333333333
#ms: 5391.880532
#1: 50000000

而你的第一次就没有了记忆，在我那台又旧又慢的笔记本电脑上

我还没有验证这个方法，但在我看来它是有效的。 您可以尝试查看它是否在某些输入上失败。我会很感激的

如果你对我如何开发这个公式感兴趣，请留下评论

我也向interviewstreet提交了解决方案，但由于时间限制，在第4个测试用例中失败了

我将很快尝试一个c程序，并在这里报告