随机取样的实现

程序的输入包含两个整数m和n,其中 m <n 。输出是 0~n-1 范围内 m 个随机整数的有序列表,不允许重复。
从概率的角度说,我们希望得到没有重复的有序选择,其中每个选择出现的概率相等。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class RandomSample {

    /**
     * 随机取样
     *
     * @param bound 样本总数
     * @param count 需要抽取的样本数
     * @return 返回一个有序数组
     */
    public static int[] getRandomSamples(int bound, int count) {
        if (count < 1 || bound <= count) {
            return null;
        }

        boolean[] fillArray = new boolean[bound];
        for (int i = 0; i < bound; i++) {
            fillArray[i] = false; //用false标示未填充,true表示已填充。
        }

        Random random = new Random();
        int fillCount = 0;
        final int randomNumCount = Math.min(count, bound - count); //随机填充的数目不超过一半
        while (fillCount < randomNumCount) {
            int num = random.nextInt(bound);
            if (!fillArray[num]) {
                fillArray[num] = true;
                fillCount++;
            }
        }

        int[] samples = new int[count];
        //如果随机抽取的数量与所需相等,则取该集合;否则取补集。
        int index = 0;
        if (randomNumCount == count) {
            for (int i = 0; i < bound; i++) {
                if (fillArray[i]) {
                    samples[index++] = i;
                }
            }
        } else {
            //取补集
            for (int i = 0; i < bound; i++) {
                if (!fillArray[i]) {
                    samples[index++] = i;
                }
            }
        }
        return samples;
    }

    /**
     * 通过洗牌的方式随机取样
     */
    public static int[] getRandomSamples2(int bound, int count) {
        if (count < 1 || bound <= count) {
            return null;
        }
        List<Integer> list = new ArrayList<>(bound);
        for (int i = 0; i < bound; i++) {
            list.add(i);
        }
        Collections.shuffle(list);
        int[] samples = new int[count];
        for (int i = 0; i < count; i++) {
            samples[i] = list.get(i);
        }
        return samples;
    }

    public static void main(String[] args) {
        int[] r1 = getRandomSamples(100, 10);
        int[] r2 = getRandomSamples2(200, 10);
        System.out.println(Arrays.toString(r1));
        System.out.println(Arrays.toString(r2));
    }

}

作者:DreamWinter
链接:https://www.jianshu.com/p/32902050f7dd
来源:简书
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。