编程珠玑 12章取样问题

输入：整数m,n

输出：成0~n-1内的m个不重复的随机整数，要求按序输出，并且保证每个子集被选中的可能性相等。

伪代码：

            select = m 

            remaining = n

            for i = (0]

                if(bigrand()%remaining) < select

                print i

                select --

           remainning --

书中p120页中的主要思想是利用《计算机程序设计艺术第2卷 半数值算法》中给出了伪代码生成数值的等概率性。下面给出java实现代码

 

package org.mino.sort;

import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Random;

/**
 * 随机获取有序数
 * @author DingJie
 */
public class RandomOrderNum {

	/**
	 * @param args
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		long beginTime = System.currentTimeMillis();
		FileWriter fw = null;
		BufferedWriter bw = null;
		try {
			fw = new FileWriter("D:/randomOrderNum.txt");
			bw = new BufferedWriter(fw);
			RandomOrderNum.getOrderRandomNum(999, 1000000, bw);
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} finally {
			if(bw != null) {
				bw.flush();
				bw.close();
			} 
			/*if(fw != null) {
				fw.flush();
				fw.close();
			}*/
		}
		long endTime = System.currentTimeMillis();
		System.out.println("总共用时(秒)：" + (endTime - beginTime) /1000);
	}
	
	/**
	 * 获取随机数
	 * @param m
	 * @param n
	 * @param ow
	 */
	public static void getOrderRandomNum(int m, int n, BufferedWriter bw) {
		Random rand = new Random(1000000);
		for(int i=0; i < n ; i++) {
			int randInt = Math.abs(rand.nextInt());
			if(randInt % (n-i) < m) {
//				System.out.println(" random: "+randInt % (n-i));
				try {
					bw.write(String.format("%d", i));
					System.out.println(i);
					bw.newLine();
					bw.flush();
				} catch (IOException e) {
					e.printStackTrace();
				}
				m --;
			}
		}
	}

}

 还有一种方法是通过m维数组，指定初始值为数组下标值的大小，然后对每一下标的值与等概率生成的下标进行交换。

 

package org.mino.perl;


import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.Random;

/**
 * 随机产生1-n的m个数
 * @author DingJie
 */
public class RandomGenerate {
	public static void main(String[] args) {
		if (args.length == 0) {
			System.out.println("请输入两个整形参数 例如 9999 1000000 ");
			return;
		}
		int m = Integer.parseInt(args[0]);
		int n = Integer.parseInt(args[1]);
		long l1 = System.currentTimeMillis();
		try {
			PrintWriter pw = new PrintWriter("D:/randomOrderNum.txt");
			random(m, n, pw);//将随机数输出
			pw.close();
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
		long l2 = System.currentTimeMillis();
		System.out.println("time:" + (l2 - l1));

	}

	static int randInt(int i, int j, Random rand) {
		if (i < j)
			return i + rand.nextInt(j - i + 1);
		return i;
	}

	/**
	 * 随机数输出到文件
	 * @param m
	 * @param n
	 * @param pw
	 */
	static void random(int m, int n, PrintWriter pw) {
		int[] array = new int[n];//最大的数组
		Random rand = new Random(System.currentTimeMillis());
		System.out.println(System.currentTimeMillis());
		for (int i = 0; i < n; i++)
			array[i] = i + 1;    //赋初值
	
		for (int i = 0; i < m; i++) {
			int j = randInt(i, n - 1, rand);//返回从i 到n-1之间的任意随机数
			int temp = array[j];
			array[j] = array[i];
			array[i] = temp;
		}
		for (int i = 0; i < m; i++) {
			pw.println(array[i]);
		}
		pw.flush();
	}
}