之前曾有人问过这个问题，但是没有一个人给出确切的答案，因此我尝试汇总在这里找到的所有信息。如有必要，可以随意合并/移动到另一个stackexchange网站。
以下是我发现的与此相关的问题:
该问题最初以Interviewstreet Code Sprint的形式发布，但现在列为a practice problem。也有ported to SPOJ。
这是问题陈述:
剧透警报-如果您想自行解决，请不要在下面阅读。
该问题可以转换为:
我采取了两种方法来解决此问题。我想到的第一个方法是:
该解决方案的复杂度为O(n/k + max_number_of_suhffles)。 Here's the actual implementation。问题是它超过了最大时间，因此我开始寻找一个公式，该公式可以让我在接近恒定的时间内获得该数字。
我在这里最能优化的(例如，使用一些映射在相同的排列周期内缓存计算值等)使它通过3/10的访谈街测试。
我发现this implementation，它假定返回到初始状态所需的随机播放次数是相对于N + 1的K的multiplicative order。
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。
这运行得非常快，但是自动评分器为我在SPOJ和Interviewstreet上的10个测试中的9个给出了“错误答案”分类。
我尝试比较两个实现的输出，但是对于我放入的测试用例(已知结果和随机)，两个实现始终输出相同的内容。这很奇怪，因为我很确定第一个算法是正确的，所以我认为第二个算法也应该是正确的。
“错误答案”分类可能来自代码中的运行时错误，但没有任何可能的原因。
我没有考虑到没有数字混洗可以使牌组恢复到初始状态的情况-我的理解是，这是不可能的。有限数量的完美混洗最终将恢复初始排序，即使混洗的数量可能确实很高。
如果您花时间阅读本文，谢谢。 :)我对此问题很好奇，我想解决它。
最佳答案
这是我在纸上进行一些观察后得出的结果。
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
虽然您的笔记本电脑在第一个笔记本电脑上就没内存了，但是在我的旧笔记本电脑上却很慢。
我尚未验证这种方法，但在我看来它确实有效。
您可能会尝试查看某些输入是否失败。我会很感激的。
如果您对我如何开发公式感兴趣，请发表评论。
我也已将解决方案提交给Transactionsstreet，但是由于时间限制，它在第4个测试用例上失败了。
我将很快尝试使用C程序，并将在此处报告。
关于java - 洗牌(SPOJ/Interviewstreet)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/12046138/