java - 如何在不使用嵌套循环的情况下解决java中的 "the birthday paradox"？

Question

我已经尝试过使用嵌套循环来解决这个问题，但是如何在不使用嵌套循环且在同一类文件中的情况下解决它。问题是求一组中两个人生日相同的概率。它应该产生以下输出:在 5 个人的小组和 10000 次模拟中，概率为 2.71%。 注意:可以使用 arraylist 或 hashmap。但我不知道怎么办。谢谢

public void process() {
    int groupSize = System.out.getSize();
    int simulationCount = System.out.getCount();

    if (groupSize < 2 || groupSize > 365) {
        System.out.makeAlertToast("Group Size must be in the range 2-365.");
        return;
    }
    if (simulationCount <= 0) {
        System.out.makeAlertToast("Simulation Count must be positive.");
        return;
    }

    double percent = calculate(groupSize, simulationCount);

    // report results
    System.out.println("For a group of " + groupSize + " people, the     percentage");
    System.out.println("of times that two people share the same birthday        is");
    System.out.println(String.format("%.2f%% of the time.", percent));

}


public double calculate(int size, int count) {
    int numTrialSuccesses = 0;

    // Repeat and count.
    for (int n=0; n < count; n++) {
        Random rand = new Random(n);
        // Generate birthdays (random array)
        int[] birthdays = new int [size];
        for (int i=0; i <size; i++) {
            birthdays[i] = rand.nextInt (365);
        }

        // Check if any two match.
        boolean matchExists = false;
        for (int i=0; i < size; i++) {
            for (int j=0; j < size; j++) {
                if ( (i != j) && (birthdays[i] == birthdays[j]) ) {
                    // Note: musn't forget the i!=j test above!
                    matchExists = true;
                    if (matchExists) break;
                }
            }
        }

        if (matchExists) {
            numTrialSuccesses ++;
        }

    } //end-for-trials

    double prob = ((double) numTrialSuccesses *100)/ (double) count;
    return prob ;

}

}

Answer 1

使用奇特数据结构HashSet的解决方案。正如评论中提到的，您可以使用 365 个 bool 元素数组，如果遇到它，您可以切换为 true。

下面是类似的想法。如果集合中尚不包含生日，则将每个生日添加到集合中。如果集合确实包含生日，则递增计数器。现在您不需要讨厌的第二次迭代，因此时间复杂度降至 O(n)。由于集合中的查找具有恒定时间，因此它可以降低到 O(n)。

public double calculate(int size, int count) {
    int numTrialSuccesses = 0;

    // Repeat and count.
    for (int n=0; n < count; n++) {
     Random rand = new Random(n);

     Set<Integer> set = new HashSet<Integer>();
        for (int i=0; i <size; i++) {
            int bday = rand.nextInt (365);
            Integer bday1 = new Integer(bday);
            if(set.contains(bday1)){
               numTrialSuccesses++;
               break;
             }else{
                 set.add(bday1);
             }
        }
    } //end-for-trials

    double prob = ((double) numTrialSuccesses *100)/ (double) count;
    //like wise comments have noted this is not the probability!!! Just a simulation
    return prob ;

}