这种洗牌算法还不是完全随机?该怎么处理
这种洗牌算法还不是完全随机?
这种洗牌算法还不是完全随机?
算法a:顺序在数组s的n个元素里填入0-(n
循环i=1到n
x=rand(n+1)
if x<>i then 交换s[i]和s[x]
据说完全随机的应该是
算法b:循环i=n到2
x=rand(i)
if x<>i then 交换s[i]和s[x]
据说原因是:算法a第1次移动后,第1个数还在第1个位置的概率是1/n,后续移动只会减少这个概率
感觉不对啊,后续移动也可能把移到别的位置的1换回第1个位置。。。。
------解决方案--------------------
包括我在内,我觉得现在的中国程序员都比较注重算法理论,但是确不重视解决当前存在的问题。
祝:1024中国程序员节快乐!
------解决方案--------------------
我建议楼主 读一下 《编程珠玑一》的12.1节到12.3节 讲一个抽样问题的。
------解决方案--------------------
后续是不可能把1在移动回1来的,仔细想一下就知道了
假定2和1换位置,之后1无论怎么换都换不回去了
------解决方案--------------------
洗牌算法参考下面:
这种洗牌算法还不是完全随机?
算法a:顺序在数组s的n个元素里填入0-(n
循环i=1到n
x=rand(n+1)
if x<>i then 交换s[i]和s[x]
据说完全随机的应该是
算法b:循环i=n到2
x=rand(i)
if x<>i then 交换s[i]和s[x]
据说原因是:算法a第1次移动后,第1个数还在第1个位置的概率是1/n,后续移动只会减少这个概率
感觉不对啊,后续移动也可能把移到别的位置的1换回第1个位置。。。。
------解决方案--------------------
包括我在内,我觉得现在的中国程序员都比较注重算法理论,但是确不重视解决当前存在的问题。
祝:1024中国程序员节快乐!
------解决方案--------------------
我建议楼主 读一下 《编程珠玑一》的12.1节到12.3节 讲一个抽样问题的。
------解决方案--------------------
后续是不可能把1在移动回1来的,仔细想一下就知道了
假定2和1换位置,之后1无论怎么换都换不回去了
------解决方案--------------------
洗牌算法参考下面:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int d[6];
int i,n,a,b,t;
int c,j;
void main() {
srand(time(NULL));
printf("shuffle 0..n-1 demo\n");
for (n=1;n<=5;n++) {/* 测试1~5个元素 */
printf("_____n=%d_____\n",n);
j=1;
for (c=1;c<=n;c++) j=j*c;/* j为n! */
j*=n*2;
for (c=1;c<=j;c++) {/* 测试n*2*n!次 */
for (i=0;i<n;i++) d[i]=i;/* 填写0~n-1 */
for (i=n;i>0;i--) {/* 打乱0~n-1 */
a=i-1;b=rand()%i;
if (a!=b) {t=d[a];d[a]=d[b];d[b]=t;}
}
printf("%04d:",c);
for (i=0;i<n;i++) printf("%d",d[i]);
printf("\n");
}
}
printf("shuffle 1..n demo\n");
for (n=1;n<=5;n++) {/* 测试1~5个元素 */
printf("_____n=%d_____\n",n);
j=1;
for (c=1;c<=n;c++) j=j*c;/* j为n! */
j*=n*2;
for (c=1;c<=j;c++) {/* 测试n*2*n!次 */
for (i=1;i<=n;i++) d[i]=i;/* 填写1~n */
for (i=n;i>1;i--) {/* 打乱1~n */
a=i;b=rand()%i+1;
if (a!=b) {t=d[a];d[a]=d[b];d[b]=t;}
}