序列随机采样问题

Programming pearls chapter 12 sampling problem

 

 从 1到n个数中随机选出m个不同的数

 

 

 

import java.util.Random;
import java.util.Set;
import java.util.TreeSet;
import java.util.Iterator;

/**

 * User: yiminghe
 * Date: 2009-2-21
 * Time: 0:27:31

 */
public class Sample {

    /**
     * 从概率学的角度 随机顺序打印 m个 1-n 个不同的数
     * i 选中概率越小 ，则 i+1 选中概率越大  ，当 m = n 是 ，上限无效
     * from : the art of computer programming ,volum2:seminumerical algorithm
     *
     * @param n
     * @param m
     */
    public static void sample1(int n, int m) {
        Random r = new Random();
        int total = n;
        for (int i = 1; m > 0 && i <= n; i++) {
            if ((r.nextInt(total) + 1) <= m) {
                System.out.print(i + "\t");
                m--;

            }
            total--;
        }
        System.out.println();

    }


    /**
     * 从概率学的角度 随机顺序打印 m个 1-n 个不同的数
     * i 选中概率越小 ，则 i+1 选中概率越大  ，当 m = n 是 ，上限无效
     * from : the art of computer programming ,volum2:seminumerical algorithm
     * 递归版本
     *
     * @param n
     * @param m
     */
    public static void sample5(int n, int m) {
        if(m<=0) return;
        Random r = new Random();
        if (r.nextInt(n) + 1 <= m) {
            System.out.print(n + "\t");
            sample5(n - 1, m - 1);
        } else {
            sample5(n - 1, m);
        }

    }


    /**
     * 随机顺序打印 m个 1-n 个不同的数
     * 集合选取元素法
     * 将选中的元素保存，随时查看
     * <p/>
     * 缺点：循环数可能很多，如果m 仅仅 n ，随机数可能会非常重复
     *
     * @param n
     * @param m
     */
    public static void sample2(int n, int m) {
        Random r = new Random();
        Set<Integer> set = new TreeSet<Integer>();
        while (m > 0) {
            int g = r.nextInt(n) + 1;
            if (!set.contains(g)) {
                m--;
                set.add(g);
            }
        }


        Iterator<Integer> iter = set.iterator();
        while (iter.hasNext()) {
            System.out.print(iter.next() + "\t");
        }
        System.out.println();

    }


    /**
     * 随机顺序打印 m个 1-n 个不同的数
     * 集合选取元素法   ,修正 sample2 ,最多 取 m 次 随机数,
     * Robert Floyd
     * 将选中的元素保存，随时查看
     *
     * @param n
     * @param m
     */
    public static void sample4(int n, int m) {
        Random r = new Random();
        Set<Integer> set = new TreeSet<Integer>();
        for (int i = n - m + 1; i <= n; i++) {
            int g = r.nextInt(i) + 1;
            if (set.contains(g))
                set.add(i);
            else
                set.add(g);
        }

        Iterator<Integer> iter = set.iterator();
        while (iter.hasNext()) {
            System.out.print(iter.next() + "\t");
        }
        System.out.println();
    }

    private static void swap(int[] ta, int i, int j) {
        int t = ta[i];
        ta[i] = ta[j];
        ta[j] = t;

    }

    /**
     * 随机顺序打印 m个 1-n 个不同的数
     * 数组顺序打乱，将前m个数和后面的数随机交换顺序
     * 将选中的元素保存，随时查看
     *
     * @param n
     * @param m
     */
    public static void sample3(int n, int m) {
        Random r = new Random();
        int t[] = new int[n];
        for (int i = 0; i < n; i++)
            t[i] = i + 1;
        for (int i = 0; i < m; i++) {
            int g = i + 1 + r.nextInt(n - i - 1);
            swap(t, i, g);
            System.out.print(t[i] + "\t");
        }
        System.out.println();

    }

    public static void main(String[] args) {
        //1到10 中随机选出三个不同的数
        sample1(10, 3);
        sample2(10, 3);
        sample3(10, 3);
        sample4(10, 3);
        sample5(10,3);
    }


}