Java生日悖论算法

Question

我对著名的生日悖论做了一个小的实现，第一次试图找到两个随机生日(这里是 1 到 365 之间的整数)之间的冲突。 但它总是返回一个大约 40 和 70 左右的值，这根本不符合统计数据。 我的算法或随机 int 生成器都有问题吗？感谢您的反馈。

代码如下:

public static void main(String[] args){
    int[] birthday = new int[200];

    for(int i = 0; i<20;i++){
        Collision(birthday); 
    }
}

public static int Collision(int birthday[]){
    Random rand = new Random();  
    for(int i = 1; i<birthday.length;i++){        
        birthday[i] = rand.nextInt(365);
    }

    int count = 0;        
    for(int i = 0; i<birthday.length; i++){          
        for(int j= i+1 ; j<birthday.length; j++){            
            if (birthday[i] == birthday[j]){               
                count++;
            }            
        }          
    }

    System.out.print(count+" ");        
    return count;  
}

这是 ex 的输出:

45 50 60 52 53 53 50 49 37 68 52 53 51 43 49 51 46 43 45 35

Answer 1

编辑:
您在算法中所做的实质是随机生成 200 个生日并计算它们之间存在多少次碰撞。

---

您知道可以使用 Set 使事情变得更简单，它在开始时是空的。然后在一个简单的 while 循环中生成生日(数字最多 365)，尝试将它们添加到 Set 中，第一次发生冲突时 - 该数字已经在 Set 中code> - 你有你的答案(答案是集合的大小)。

也就是说，如果您的目标真的是找到最少生日数的碰撞。

例如，这个:

Random rand = new Random();
for (int t = 0; t < 20; t++)
{
    Set<Integer> b = new HashSet<Integer>();
    while (true)
    {
        int n = rand.nextInt(365);
        if (!b.add(n))
            break;
    }
    System.out.print(b.size() + " ");
}

产生:

15 30 24 4 8 19 10 40 32 31 30 14 41 30 15 7 15 52 24 27