More Programming pearls
做习题:用你最喜欢的编程语言实现Floyd算法。
1 - n 中随机取m个数组成集合
1 - n 中随机取m个数组成序列
演示@google code
javascript实现以及证明,更简洁优雅
<script type="text/javascript">
if(!window.console) {
window.console={};
window.console.log=function(v){
alert(v);
};
}
if(!Array.prototype.indexOf) {
Array.prototype.indexOf = function(v){
for(var i=0;i<this.length;i++)
if(this[i] === v) return i;
return -1;
}
}
function randIt(l,u){
return l+Math.floor(Math.random()*(u-l+1));
}
/*
1 - n 中随机取m个数组成集合
*/
function randomSet(m,n) {
var start=n-m+1;
var holder={};
for(var i=start;i<=n;i++) {
//random 1~i not 1~i-1
var cur=randIt(1,i);
if(holder[cur]) {
holder[i]=1;
} else {
holder[cur]=1;
}
}
return holder;
}
/*
1 - n 中随机取m个数组成序列
*/
function randomList(m,n) {
var start=n-m+1;
var holder=[];
for(var i=start;i<=n;i++) {
//random 1~i not 1~i-1
var cur=randIt(1,i);
//trick tick
var position=holder.indexOf(cur)+1;
var insert=position?i:cur;
holder.splice(position,0,insert);
}
return holder;
}
(function main(){
var set=randomSet(5,10);
var t=[];
for(var i in set) {
t.push(i);
}
console.log("*******************Random Set :\n"+t);
var list=randomList(5,10);
console.log("*******************Random List :\n"+list);
})();
/*
证明:
list :
对于任何一个序列,有且仅有一种途径来生成它,因为算法是可以逆推的。
例如M=5,n=10,且最终序列为
7 2 9 1 5
由于 10 (i的最终值)不在s中出现,所以之前的序列为 2 9 1 5,且之前随机数为 7 ,
类似可以推出之前每步产生的随机数,
由于假定随机数的序列是随机产生的,则该程序算法所生成的序列也是随机生成的。
set:
每一个m元集合都有m!的序列生成,序列是等概率的,则集合也是等概率的。
*/
</script>
Java 实现
: 序列随机采样问题
- 大小: 2.8 KB
分享到:
相关推荐
WebGL 是一项在网页浏览器呈现3D画面的技术,有别于过去需要安装浏览器插件,通过 WebGL 的技术,只需要编写网页代码即可实现3D图像的展示。WebGL可以为 HTML5 Canvas 提供硬件3D加速渲染,这样 Web 开发人员就可以...
绝妙好词
Gauss在1827年10月27日发表的论文,开启了微分几何的新世界
Excel模板绝妙企业通讯录.zip
0欧姆电阻的用处,这里例句了一些,其实是比较常用的,望大家共同学习
Nginx + PHP-FPM + APC=绝妙的组合 Nginx + PHP-FPM + APC=绝妙的组合 Nginx + PHP-FPM + APC=绝妙的组合 Nginx + PHP-FPM + APC=绝妙的组合
古今绝妙对联大全.doc
EXCEL教程-绝妙.pdf
世界营销绝妙点子.doc
小学数学数学神探绝妙判决
企业公司的绝妙工资条
绝妙企业通讯录
满分作文绝妙开头示范.doc
初中语文文摘文苑绝妙的回答
绝妙企业通讯录excel模版下载.xlsx
营销绝妙金点子800例.doc
风河工程师写的绝妙嵌入式系统书籍
绝妙的VFP高级指南、普通指南,对你的编程也许有些帮助吧,O(∩_∩)O哈哈~
英语知识绝妙的13个口诀.doc