e***l
发帖数: 710 | 1 以下算法可以产生均匀的随机数组（<=>表示交换）
for i=1 to n, A[i] <=> A[rand(i..n)] ---方法A
那么这个算法呢
for i=1 to n, A[i] <=> A[rand(1..n)] ---方法B |
f***g
发帖数: 214 | |
e***l
发帖数: 710 | |
z**c
发帖数: 625 | 4 这个其实很直观，i前面的相当于已经摆好的；i后面的继续随机。你如果跟整个数组随
机选一个出来交换，那之前的部分结果不都破坏了嘛。
【在 e***l 的大作中提到】
: 以下算法可以产生均匀的随机数组（<=>表示交换）
: for i=1 to n, A[i] <=> A[rand(i..n)] ---方法A
: 那么这个算法呢
: for i=1 to n, A[i] <=> A[rand(1..n)] ---方法B
|
e***l
发帖数: 710 | 5 对于这个不对的算法 for i=1 to n, A[i] <=> A[rand(1..n)]
怎么严格证这样不是均匀的？楼上只能说明之前的证法行不通。
我试图去证原始的那个排列shuffle后出现的概率不等于1/n!，但没想出来 |
t****0
发帖数: 235 | 6 zt
- the first card can be in 52 ways, the second in 51 ways etc...
So, there are 52 * 51 * 50 * ... 1 ways!
i.e. 52! ways
( 52 factorial) ways |
e***l
发帖数: 710 | 7 理论上最多只有n!种排列，所以n^n中有重复的，因为n^n>n! |
l*********r
发帖数: 674 | 8 为什么非要可能排列的1/n!呢？如果从单个A[i] 的概率来说，两种不都是1/n么？
shuffle的目的不就是要让每个位置都是1/n么？
【在 e***l 的大作中提到】
: 理论上最多只有n!种排列，所以n^n中有重复的，因为n^n>n!
|
|
F**********r
发帖数: 237 | 9 请教crls是啥？
【在 f***g 的大作中提到】
: 不行，看CRLS
|
e***l
发帖数: 710 | 10
每个位置1/n不充分。见习题5.3.4
1/n!等概率是均匀随机序列的定义，即每种排列出现的概率相等，都等于1/n!
CRLS就是算法导论那本书
【在 l*********r 的大作中提到】
: 为什么非要可能排列的1/n!呢？如果从单个A[i] 的概率来说，两种不都是1/n么？
: shuffle的目的不就是要让每个位置都是1/n么？
|
q******g
发帖数: 31 | |
i****d
发帖数: 35 | 12 反证
如果第二个是等概率的，那么 n! | n^n
但是后面这个式子不成立
因此不对
【在 e***l 的大作中提到】
: 以下算法可以产生均匀的随机数组（<=>表示交换）
: for i=1 to n, A[i] <=> A[rand(i..n)] ---方法A
: 那么这个算法呢
: for i=1 to n, A[i] <=> A[rand(1..n)] ---方法B
|
