java - 洗牌(SPOJ/Interviewstreet)

Question

这个问题以前有人问过，但是没有一个得到明确的回答，我试着编译我在这里找到的所有信息。如有必要，请随意合并/移动到另一个 stackexchange 站点。

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

• SPOJ:Card Shuffling
• Card Shuffling [SPOJ]

该问题最初作为 Interviewstreet Code 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 + max_number_of_suhffles)。 Here's the actual implementation .这样做的问题是它超过了最长时间，所以我开始寻找一个可以让我在接近常数的时间内获得数字的公式。

我在这里可以优化的最多(例如，使用一些映射在相同的排列周期中缓存计算值等)是让它通过 interviewstreet 上的 3/10 测试。

---

我找到了 this implementation ，假设返回初始状态所需的洗牌次数为 multiplicative order K 相对于 N + 1。来自 wiki:

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

φ(n) 是 Euler totient function , ordn 是 group order - 我们正在寻找什么。我找到了 this paper它使用 φ 来计算洗牌次数，但它仅适用于 2-way in-shuffle，而不是 k-way。

以下是此实现的步骤:

• 预先计算了 < 100 000 个素数的列表
• 根据其质因数计算φ(N+1)。
• 通过以所有可能的方式组合主要因子来确定所有φ(N + 1) 的因子。
• 依次尝试每个因素并得到最小的一个，x，这验证了k ^ x % N + 1 = 1

这个实现也是posted on GitHub .

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

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

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

我没有考虑没有数字洗牌可以将牌组恢复到初始状态的情况 - 我的理解是这是不可能的。有限次数的完美洗牌最终会恢复初始顺序，即使洗牌次数可能非常多。

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

Answer 1

这是我在纸上进行一些观察后得出的结论。

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 程序，并会在这里报告。