随机抽样算法

<?php
/**
 * 程序的输入包含两个整数m和n，其中m<n。
 * 输出是0~n-1范围内m个随机整数的有序列表，不允许重复。
 * 从概率的角度来说，我们希望得到没有重复的选择，其中每个选择出现的概率相等。
 * 算法源自Knuth的《计算机程序设计艺术 第2卷 半数值算法》。
 * Knuth 给出了概率上的证明，每个数选中的概率都是m/n，而且恰好选中m个数
 */

function GenerateKnuth($m, $n){
    for( $i=0; $i<$n; $i++ ){
        if( rand(0, $n-$i-1) < $m ){//以m/(n-i)的概率执行下面的语句
            printf("%d\n", $i);
            //echo "-------n:".$n.' i:'.$i.' m:'.$m,'<br/>';
            $m--;
        }
    }
}

GenerateKnuth(5, 100);
//GenerateKnuth(15, 100);

/**
 * 蓄水池抽样法
 * 给你一个长度为N的链表。N很大，但你不知道N有多大。
 * 你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。
 * 你的算法必须保证取出的元素恰好有k个，且它们是完全随机的（出现概率均等）。
 */

/**
 * 蓄水池抽样法1
 * sql中的ORDER BY RAND (随机抽取)
 * 对于集合中的每一个元素，都产生一个0-1的随机数，之后选取随机值最大的前k个元素
 */
function ReservoirSampling1($m, $n){
    $array = array();
    for ($i=0; $i<$n; $i++){
        $rand = rand(0, 99999999)/100000000;//生成一个0-1之间的随机数
        //echo $rand,chr(10);
        $array[$i] = $rand;
        if(count($array) > $m){//数组超过蓄水池容量则按随机数排序最后一个出栈
            arsort($array);
            array_pop($array);
        }
        //print_r($array);
    }
    print_r(array_keys($array));
}

ReservoirSampling1(10,1000);

/**
 * 蓄水池抽样法2
 * 先构建一个可以放m个元素的蓄水池
 * 将前m个数依次放入，从第m+1个元素开始，以m/n的概率决定元素是否被替换到池子中
 * 当遍历完所有的的元素后，及得出随机挑选的k个元素，时间复杂度为O(n)
 */
function ReservoirSampling2($m, $n){
    $array = array();
    for ($i=0; $i<$n; $i++){
        if(count($array) >= $m){
            if( rand(1, $i) < $m ){//1/i的概率执行下面的语句
                $array[rand(0, $m-1)] = $i;//随机替换蓄水池中的一个数为当前值
            }
        }else
            $array[$i] = $i;
    }
   
    print_r($array);
}

ReservoirSampling2(10, 1000);