随机取数使概率相等

小半 • 2023年2月3日上午10:47 • 技术随笔 • 阅读 208

题目：随机地从大小为n个数中选取m个数。要求每个元素被选中的概率相等？

分析：这道题目和随机洗牌算法类似，只需要随机选取1个元素，然后在剩下的元素里面随机选取下一个元素，不断这样操作即可。

这样做能保证每个元素选中的概率一样吗？也就是选中每个元素的概率都是1/n？答案是YES，让我们来做一下简单的计算。

选第1个元素：在n个中随机选，因此概率为1/n

选第2个元素：在剩下的n-1个中随机选：1/(n-1)，由于第1次没有选中它，而是在另外n-1个中选：(n-1)/n，因此概率为：(n-1)/n * 1/(n-1) = 1/n

选第3个元素：同上：(n-1)/n * (n-2)/(n-1) * 1/(n-2) = 1/n

。。。。。

思路：
由于Random的nextInt(x) 方法是从 0 到 x-1 随机取数，所以使random的数视为从数组从后往前倒着数的索引；
第一次 i=0 ，首先在索引0 到 n-1 共n个数之间取一个数，即 j= nextInt(n)，抽出来的数的索引是 n-1-j，然后将这个下标对应的数和数组的i=0 处数交换位置；
然后i=1时，从1到n-1共n-1个数之间用nextInt() 方法随机取一个数，nextInt()是从0到n-2取所以是nextInt(n-1)，然后将下标对应的数和数组的第二个数交换位置。依次这样下去，知道找出m个数。

注意：
Random对象的 nextInt(x) 方法，随机从0到x-1 之间取数，不包括 x ！

public class test02 {
    static List<Integer> r=new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String s1 = in.readLine();
        String s2 = in.readLine();
        int n = Integer.parseInt(s1);
        int m = Integer.parseInt(s2);
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = i;
        }
        select(nums, m);
        for(int k:r){
            System.out.println(k);
        }

    }

    static void select(int[] nums, int m) {
        int n=nums.length;
        for (int i = 0; i < m; i++) {
            // Random.nextInt(x) 随机筛选0到x-1之间的数 ！
            // 每次筛选以i为起点，所以实际筛出来的数的索引是  n-1-筛的索引
            int randomindex=n-1-new Random().nextInt(n-i);
            r.add(nums[randomindex]);
            //交换
            int temp=nums[i];
            nums[i]=nums[randomindex];
            nums[randomindex]=temp;
        }
    }
}