问题描述
考虑以下算法，该算法生成数字1到N的（不一定是统一的）随机排列：
Consider the following algorithm, which generates a (not necessarily uniformly) random permutation of numbers 1 through N:
P := [1, 2, ..., N]
for i in 1..N do
j := rand(1, N)
swap(P[i], P[j])
这里，rand（1，N）返回1到N之间的均匀随机整数。让我们表示这个算法产生的置换是P乘以p（P）的概率。
求一个置换P1使得p（P1）是最大可能的排列P2使得p（P2）是最小的。
我尝试过：
我粗暴地强迫它直到N = 7并且使用预先计算回答但是对于更大的N（N
如何实现此代码？
否则，是否有计算数字在非均匀线性混洗中的特定指数结束的概率的任何公式？
Here, rand(1, N) returns a uniformly random integer between 1 and N inclusive. Let's denote the probability that the permutation generated by this algorithm is P by p(P).
Find a permutation P1 such that p(P1) is maximum possible and a permutation P2 such that p(P2) is minimum possible.
What I have tried:
I brute-forced it till N=7 and answering using precalculation but for larger N (N<=17) ot gets stuck. O(N^17)!
How can I implement this code?
Else, is there any formula to calculate the probability that a number ends at a particular index in a non-uniform linear shuffle?
推荐答案
这篇关于如何为更大的数字实现这个算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！