算法问题：怎样得到n个元素的随机排列？

Question

对了，最好先输出一遍，看看结果
document.write(array1+"<br>"+getRndArray(array1))

Answer 1

这个是我的，想不到居然还比较快。看来大家要将jstest取大一点了。
function getRndArray(arr0){
//这里写你的函数
arr1=new Array();
len=arr0.length;      
for(var i=0;i<len;i++){
rnd=Math.floor(Math.random()*arr0.length);
arr1[i]=arr0[rnd];
arr0.splice(rnd,1)
}
return arr1;
}

Answer 2

function getRndArray(arr){
//这里写你的函数
return arr.sort(foo);
}
function foo(a,b) {
  return Math.random()>0.5 ? 1 : -1;
}
做完这件事需要69700毫秒
P2/133 64M 用  wzhiyuan(我是谁) 的算法
做完这件事需要270毫秒
P2/133 64M 还有再快的吗？

Answer 3

用  wzhiyuan(我是谁) 的算法
function alertTest()
{
var jsBegin = new Date().getTime(); 
var array1=new Array();
for (i=0;i<100;i++)
array1[i]=i;
var jstest =  10000;
for(var i=0;i<jstest;i++){
   result = getRndArray(array1);
}var jsEnd = new Date().getTime(); 
document.write("做完这件事需要" + (jsEnd - jsBegin)  + "豪秒<br/>");}
function getRndArray(arr0){
//这里写你的函数
arr1=new Array();
len=arr0.length;      
for(var i=0;i<len;i++){
rnd=Math.floor(Math.random()*arr0.length);
arr1[i]=arr0[rnd];
arr0.splice(rnd,1)
}
return arr1;
}做完这件事需要47豪秒
赛扬 2.66 256M看来配置好坏差很远啊！

Answer 4

<script language="JavaScript">
<!--
var array1=new Array();
for(var i=0;i<10000;i++){
array1[i]=i;
}
Array.prototype.Random=function()  {
for(var i=0;i<this.length;i++){
var rnd=Math.floor(Math.random()*this.length)
var swap=this[i];this[i]=this[rnd];this[rnd]=swap;
}
return this
}
alert(array1.Random())
//-->
</script>

Answer 5

fason(咖啡人生) 的算法是对的，
其实这个就是扑克洗牌用的算法，
随机找一个元素和该元素对调。

Answer 6

我这个算法明显比fason(咖啡人生) 的慢，也拿出来参考一下
<script language="JavaScript">
<!--
var array1=new Array(100);
for(var i=0;i<array1.length;i++){
array1[i]=i;
}Array.prototype.Random=function()  {
  var ret=new Array(0);
  for(var i=this.length;i>0;i--){
var rnd=Math.floor(Math.random()*this.length);
ret[ret.length]=this[rnd];
this.splice(rnd,1);
  }
  return ret;
}
var tstart=new Date().getTime();
var array2=array1.Random()
var tend=new Date().getTime();
alert(array2+"\n***************花费时间为 "+(tend-tstart)+" 毫秒")
//-->
</script>

Answer 7

只要不重新分配内存,速度就上来了,删除数组元素其实就在重新分配内存.我的方法是重新不分配内存的.function getRndArray(array1){
var tLen=array1.length
var tMax=tLen
var i
var tSwap
var tIdx

for(i=0;i<tLen;i++){
tIdx=Math.floor(Math.random()*tMax)
tSwap=array1[tMax-1]
array1[tMax-1]=array1[tIdx]
array1[tIdx]=tSwap
tMax-=1
}

return array1
}

Answer 8

我的方法还有改进的地方,既然是两两交换,那100个元素只要交换50次就可以了,不用100次,呵呵,运行时间再次减半!
function getRndArray(array1){
var tLen=Math.floor(array1.length/2)
var tMax=tLen
var i
var tSwap
var tIdx

for(i=0;i<tLen;i++){
tIdx=Math.floor(Math.random()*tMax)
tSwap=array1[tMax-1]
array1[tMax-1]=array1[tIdx]
array1[tIdx]=tSwap
tMax-=1
}

return array1
}

Answer 9

function getRndArray(array1){
var tMax=array1.length
var tLen=Math.floor(tMax/2)
var i
var tSwap
var tIdx

for(i=0;i<tLen;i++){
tIdx=Math.floor(Math.random()*tMax)
tSwap=array1[tMax-1]
array1[tMax-1]=array1[tIdx]
array1[tIdx]=tSwap
tMax-=1
}

return array1
}

Answer 10

我的办法虽然慢，但是可以通过严格分析证明：任意一个元素落在每个位置的概率是相等的。fason(咖啡人生) 的办法，表面是可以的，但证明很困难 LGEN() ( )的办法跟fason(咖啡人生)本质是一样的，但是折半后，概率就不均等了，所以折半是不行的

Answer 11

to cxz7531(大花猫)
我的方法和fason(咖啡人生)最大的不同是我多个一个变量tMax.
这个变量,起到的作用就和你的splice一样.比如有1,2,3,4四个数,一开始tMax=4
那末随机序号的范围是1..4,我随机挑一个数放到最后.
第二次时,tMax=3
那末随机序号的范围是1..3,我随机挑一个数放到最后.
第二次时,tMax=2
那末随机序号的范围是1..3,我随机挑一个数放到最后.
......
这样就不会产生被移动过的元素再次被移动的可能.就和splice的作用一样.可惜splice要重新分配内存,这就是瓶颈.
这也可以说明,交换次数为Array.length/2是正确的,否则每个元素要被移动2次,既然第一次就是随机的,那第2次就没有意义了

Answer 12

写出来了
哈哈~~~~
<script language="javascript">var array1=new Array();
var temp,n='';
for(var i=0;i<10;i++)
{
array1[i]=i;
}
var len=array1.length;
for(var j=0;j<len;j++)
{
var m=Math.random()*len;
var nn= Math.ceil(m);
for(var i=j;i<len;i++)
{
if(array1[i]==nn)
{
temp=array1[i];
array1[i]=array1[j];
array1[j]=temp;
}
}
}
for(var i=0;i<10;i++)
{
n+=array1[i];
}
alert(n)
</srcript>

Answer 13

to LGEN() ( )
-----------------------
 但是折半后，第一个元素再也无法走到第二个位置
比如 原始数组是  0 1 2 3 4    5  6 7 8 9   在这个情况下 0不会落在 1 2 3 4的位置，而只会落在 5  6 7 8 9 的位置

Answer 14

改进一下
这样子,从800毫秒,变为500毫秒var array1=new Array();
var temp;
var n='';for(var i=0;i<1000;i++)
{
array1[i]=i;
}
var len=array1.length;
var jsBegin = new Date().getTime();
for(var j=0;j<len;j++)
{
var m=Math.random()*len;
var nn= Math.ceil(m);
for(var i=j;i<len;i++)
{
if(array1[i]==nn)
{
temp=array1[i];
array1[i]=array1[j];
array1[j]=temp;break;
}
}
}
var jsEnd = new Date().getTime(); for(var i=0;i<10;i++)
{
n+=array1[i];
}
alert(n)
alert("做完这件事需要" + (jsEnd - jsBegin)  + "豪秒");

Answer 15

to LGEN() ( )
-------------
交错也是没有理论依据的，还是老兄刚开始没有折半的办法好，比咖啡人生的还要快很多
我稍微修改了一下。
经过测试：1000个数，耗时小于1毫秒；10000个数，耗时63毫秒，速度应该时最快的
<HTML>
<HEAD>
</HEAD>
<script language="JavaScript">
<!--
var array1=new Array(1000);
for(var i=0;i<array1.length;i++){
array1[i]=i;
}function getRndArray(array1){
  var tLen=array1.length
  var tMax=tLen
  var i
  var tSwap
  var tIdx
  while(tMax>0){
   tIdx=Math.floor(Math.random()*tMax)
   tSwap=array1[tMax-1]
   array1[tMax-1]=array1[tIdx]
   array1[tIdx]=tSwap
   tMax-=1
  }
  return array1
}
var tstart=new Date().getTime();
getRndArray(array1);
var tend=new Date().getTime();
alert("\n***************花费时间为 "+(tend-tstart)+" 毫秒")
//-->
</script>
<BODY>
</BODY>
</HTML>

Answer 16

function window_onload() {
var arr = new Array();
for(var i=0;i<100;i++) {
arr[i] = i;
}
var jsBegin = new Date().getTime(); 
var jstest =  1000;
for(var i=0;i<jstest;i++){
getRndArray(arr);
}
var jsEnd = new Date().getTime(); 
document.write("做完这件事需要" + (jsEnd - jsBegin)  + "豪秒<br/>");
}function getRndArray(arr){
var tmp;
var pos;
for(var i=arr.length-2;i>=0;i--) {
pos = Math.floor(Math.random()*i);
tmp = arr[i+1];
arr[i+1] = arr[pos];
arr[pos] = tmp;
}
return arr;
}

Answer 17

看来看去,偶的算法还有毛病,主要是取随机数时
改成下面的可以了
不过效率倒没提高
var array1=new Array();
var temp;
var n='';for(var i=0;i<1000;i++)
{
array1[i]=i;
}
var len=array1.length;
var mm=array1.length;
var jsBegin = new Date().getTime();
for(var j=0;j<len;j++)
{
var m=Math.random()*mm;
mm--;
var nn= Math.ceil(m); for(var i=j;i<len;i++)
{
if(array1[i]==nn)
{
temp=array1[i];
array1[i]=array1[j];
array1[j]=temp;break;
}
}
}
var jsEnd = new Date().getTime(); for(var i=0;i<10;i++)
{
n+=array1[i];
}
//alert(n)
alert("做完这件事需要" + (jsEnd - jsBegin)  + "豪秒");

Answer 18

to   tigeryu(吴越小虎) ( ) 信誉：100  2005-03-18 14:05:00  得分: 0  
   楼上你的函数才执行了一遍，人家是执行一万遍的速度，麻烦你看仔细一点
------------------
我的函数执行一遍得到n个数的一个随机排列，耗时小于1ms。谁的速度是得到10000个随机排列的速度？？

Answer 19

今天事比较多，没仔细研究，只大致看了一下。
cxz7531(大花猫) 的算法和我的几乎一样,大家看一下。
这个是我的，
function getRndArray(arr0){
//这里写你的函数
    arr1=new Array();
    len=arr0.length;      
   for(var i=0;i<len;i++){
       rnd=Math.floor(Math.random()*arr0.length);
       arr1[i]=arr0[rnd];
       arr0.splice(rnd,1)
   }
   return arr1;
}
这个是 cxz7531(大花猫)的，
Array.prototype.Random=function()  {
  var ret=new Array(0);
  for(var i=this.length;i>0;i--){
  var rnd=Math.floor(Math.random()*this.length);
  ret[ret.length]=this[rnd];
  this.splice(rnd,1);
  }
  return ret;
}
不同仅在于我的是函数，cxz7531(大花猫）写成了数组的方法。效率吗，自然是写成数组方法快一点。但快得有限（不到10%）。但我们都犯了一个错误。只执行一次，代码没任何问题。但我们都是在源参数对象上直接改的（我的arr0.splice(rnd,1),大花猫的this.splice(rnd,1);），执行过一次之后，源参数数组变为了空。所以看似执行了10000次，实际上是一次。我将算法改了一下，加了一个temparray=arr0.slice(0),即复制到临时数组，然后在临时数组上改。经这样改了之后，执行1000次循环，cxz7531(大花猫）的数组方法执行时间是5400豪秒，我的函数是5800豪秒.
 fason(咖啡人生) 的洗牌算法也是写成了数组方法，为了统一比较算法优劣，我改成了函数如下；
function getRndArray(arr0){//改自fason(咖啡人生) 的洗牌算法
tempArray=arr0.slice(0);
len=tempArray.length;
for(var i=0;i<arr0.length;i++){
var rnd=Math.floor(Math.random()*len)；
var swap=tempArray[i];
                           tempArray[i]=tempArray[rnd];
                           tempArray[rnd]=swap;
}
return tempArray
}
同样1000次，执行时间是1100豪秒。不过，就象cxz7531(大花猫)说的那样，我们的抽取算法（从集合中按顺序随机抽取元素）得到的新排列是和上一次排列完全独立的。而
fason(咖啡人生)的洗牌算法，所得到的新排列，则是在上一次的排列基础上交换而来，从理论上来说，有限次的交换，总不能得到“真正”的随机排列。不过，从应用的角度来讲，比较多次的交换，也可以得到比较满意的结果，而且效率又比较高，所以实用价值可能更大。
下面朋友的算法我还没细看，周末两天在家不能上网，所以只能到下周一再研究了。有兴趣的朋友，请继续支持。谢谢。

Answer 20

今天有空又看了一下，觉得LGEN() 的算法才是对的。
他的同 fason(咖啡人生) 的不同就在于取随机数。
fason(咖啡人生)的是这样取的，
var rnd=Math.floor(Math.random()*this.length)
（事实上在循环里象this.length这样每次都用属性是一种低效的用法，应该先赋给变量）
LGEN() 的取随机数是这样取的，
tIdx=Math.floor(Math.random()*tMax)
其中tMax是个每次循环递减的变量，说明每次交换到后面的元素相当于已经取出。这种思想和我原来的splice()是一样的。不过就象LGEN()解释的，splice的做法要分配内存，所以比较慢。LGEN()后来的折半之类，则只是交换，没有了抽取的思想，所以我认为是不正确的。flyskytoday(路要靠自己走.光风) 的算法，老实说，没看懂。比如里面有这样的句子:
if(array1[i]==nn)
这不是拿元素和随机数比较吗？我说过了，这里数组元素取为纯数字，只是为了构造方便，不应该从元素的特点着手。xuzuning(唠叨) 的数组排序我不大懂。
function getRndArray(arr){
//这里写你的函数
return arr.sort(foo);
}
function foo(a,b) {
  return Math.random()>0.5 ? 1 : -1;
}
各位有懂的热心人，加我qq28368672给我讲解一下，谢谢。在上面各位，主要是LGEN()的基础上，我又将算法写了一下，算作总结，各位还有其它方法的可以继续跟贴。没有的话我17:00结贴。
function getRndArray2(arr0){
         //对输入数组进行随机排列
len=arr0.length;
var rnd,swap;
for(var i=0;i<len;i++){
rnd=Math.floor(Math.random()*(len-i))+i;
         //比之LGEN()的写法省了一个变量tMax，并相应少了一句tMax-=1，时间又少了一点，呵
swap=arr0[i];arr0[i]=arr0[rnd];arr0[rnd]=swap;
}
return arr0;
}

Answer 21

同意：“ 回复人： fason(咖啡人生) ( ) 信誉：705  2005-3-17 17:26:59  得分: 30  ”
这种算法每一次调换同时是两个随机操作：
1.取某个数，（平均分布的）随机扔向任意位置
2.（平均分布的）随机取任意一数，放到某个位置
相当于一次随机”抽”＋“调“一个循环下来，每一个数至少被随机或抽或调过一次，
抽调过一次的数的位置是（平均分布）随机的，不管它以后再被抽调多少次。个人看法，以咨参考

Answer 22

回复人： LGEN() ( ) 信誉：86  2005-3-18 9:59:39  得分: 45  
----
这个洗牌算法是（平均分布）随机的，（感觉是这样的，没有详细证明）
不过没理由会比fason的方法快－－－－－－－－－－－－－－－－－－回复人： LGEN() ( ) 信誉：86  2005-3-18 10:02:32  得分: 0  
”既然是两两交换,那100个元素只要交换50次就可以了,不用100次“
----
指导思想错误，
如果只换50次，那么０在洗牌后的位置一定不是第一个元素，
但是洗牌的结果是０在洗牌后的位置得第一个数的可能性是存在的（为：1/牌数）－－－－－－－－－－－－－－－－－－
回复人： xuzuning(唠叨) ( ) 信誉：671  2005-3-17 16:44:54  得分: 16  
----
时间复杂度大，

Answer 23

fason的代码也可以稍作修改，
效率不见得会提高，
但是算法合理性的证明可能要简单一点（直接用数学归纳法就可以了）<script language="JavaScript">
<!--var array1=new Array(10000);Array.prototype.Random=function()  {
for(var i=0;i<this.length;i++){
var rnd=Math.floor(Math.random()*(i+1))
this[i]=this[rnd];
this[rnd]=i;
}
return this
}
document.write(array1.Random())-->
</script>

Answer 24

i+1
--->>>>
i+0.99999