一道有趣的概率算法题！ 欢迎大家前来讨论
有一初始数组A= <1,2,3,4> 并选择随机的优先级P= <36,3,97,19> 这样得出数组B= <2,4,1,3> 因为第2个优先级最小,接着是第4个,然后是第1个,最后是第3个.
现假设是从1到n^3之间的随机数.在此范围内是为了让P的所有优先级尽可能唯一. 那么使所有元素都唯一的概率是多少?
请各位写出解答过程
感谢各位的参加
[解决办法]
令 N=n^3 (仅为书字方便)
即P中的元素为1至N之间的随机数
我们使用f(x)表示P中有x个元素时, 无重复元素的概率
则: f(1) = 1 = N/N
f(x+1) = f(x) * (N-x) / N
增加每x+1个元数时, 此元互与前面x个元素不重复的概率为 (N-x)/N
很容易推出 f(n) = N!/((N-n)! * N^n)
[解决办法]
ls正解，生日悖论就是这么推导的；
我觉得也可以这么理解：
所有N个数可重复取的排列总数为 N^n;
所有N个数不可重复取的排列总数为 N!/(N-n)!
所以概率为：
N!/(N-n)! / N^n
==N!/((N-n)! * N^n)
