学步园

背景：有个存有1000个问题的题库，用数组numHastack存，现要从中随机生成5道题。如果直接用随机数生成函数rand（）,然后把生成的题号存到数组numGenerate中，会产生重复出现的问题。

参考我原来的博文：http://blog.csdn.net/wusuopubupt/article/details/8823145

1.最直接的解决办法:

每随机生成一个数，就拿到数组numGenerate中比较，如果存在，就重新rand，否则push到数组中，知道数组长度达到5.

这里关键就是借助in_array()函数判断num是否在array中。

<?php 
$numGenerate = array();
$max = 1000;
for($i = 0;$i < 5;$i++){
    $num = mt_rand(0,$max);
    while(in_array($num, $numGenerate)){
    	$num = mt_rand(0, $max);
    }
    
    $numGenerate[$i] = $num;
}

var_dump($numGenerate);
?>

2 用shuffle函数，把固定的数组打乱，然后，选择前5个即可

shuffle函数原理：http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

                              http://www.cnblogs.com/futuredo/archive/2012/10/23/2735686.html

我写的shuffle函数

<?php
$times = 100;
function my_shuffle() {
	global $times;
	$arr = range(0,9);
	//var_dump($arr);
	for($i = 0;$i <= $times;$i ++){
		$num = mt_rand(0, 9);
		$temp = $arr[$num];
		$arr[$num] = $arr[0];
		$arr[0] = $temp;
	}
	return $arr;
}

var_dump(my_shuffle());

shuffle实现最终版：

<?php 
$numHastack = array();
$numGenerate = array();
$max = 1000;

//better method: range(0,1000)
for($i = 0;$i <$max;$i++){
    $numHastack[] = $i;
}

shuffle($numHastack);
for($i =0;$i < 5;$i++){
	$numGenerate[]= $numHastack[$i];
}

var_dump($numGenerate);
?>

3.借助于hashtable（相当于每个数都对应一个flag），不到数组numGenerate中比较，而是用while循环检查hashtable[num] 的值是否为0（，没去过是默认为0，取过则设为1），如果不为0，则重新生成num,知道hashtable[num] == 0;

<?php 
$hashtable = array();
$numGenerate = array();
$max = 1000;
for($i = 0;$i < 5;$i++){
    $num = mt_rand(0,$max);
    while(@$hashtable[$num] > 0){
    	$num = mt_rand(0, $max);
    }
    
    $numGenerate[$i] = $num;
    $hashtable[$num] = 1;
}

var_dump($numGenerate);
?>

4.速度最快的算法（不做比较，只做交换）

<?php
/**
*generate 5 random numbers from total 1000 without duplicate 
*
* 
*/
$min = 0;
$max = 1000;
$numHastack = array();
$numGenerate = array();
for($i= 0;$i <= $max;$i++){
	$numHastack[$i] = $i; 	
}
var_dump($numHastack);
for($i = 0;$i < 5;$i++){
	echo $max;
	$randIndex = mt_rand(0,$max);
	$numGenerate[$i] = $numHastack[$randIndex];
	$numHastack[$randIndex] = $numHastack[$max];
	$max--;		
}
var_dump($numGenerate);

参考文献：http://www.cnblogs.com/eaglet/archive/2011/01/17/1937083.html

特别鸣谢：张亚杰同学http://www.cnblogs.com/buptpatriot