CODEWITHSUNDEEP
javaalgorithmrandom
loukios
loukios

Reputation: 245

Java birthday paradox algorithm

I've made a small implementation of the famous birthday paradox, trying to find a collision between two random birthdates (here integer between 1 and 365) for the first time. But it returns always a value around let's say 40 and 70, which does not fit the stats at all. Is something wrong with my algo, or with the random int generator, both ? Thanks for your feedback.

Here is the code :

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;  
}

Here is the output for ex :

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

Upvotes: 2

Views: 2739

Answers (3)

Bohemian
Bohemian

Reputation: 425458

Your algorithm seems OK and the results are reasonable.

FYI you could use streams to very efficiently do all the heavy lifting in 1 line:

private static Random rand = new Random(); 
public static int collision(int size) {
    return size - Stream.generate(() -> rand.nextInt(365)).limit(size).distinct().count();
}

And a 1-line main:

public static void main(String[] args){
    Stream.of(200).map(MyClass::collision).forEach(System.out::println);
}

Upvotes: 0

radoh
radoh

Reputation: 4825

EDIT:
What you essentially did in your algorithm is that you generated 200 random birthdays and counted how many collisions exist among them.

You know you could make things a lot simpler by using a Set, which is empty at the beginning. Then in a simple while loop generate birthdays (numbers up to 365), try adding them in the Set, and the first time you get a collision - the number is already in the Set - you have your answer (the answer being the size of the Set).

That is, if your goal really is to find a collision in minimum number of birthdays.

E.g., this: 

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() + " ");
}

Produces:

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

Upvotes: 5

Bathsheba
Bathsheba

Reputation: 234885

Your numbers look fairly reasonable.

But you are repeatedly instantiating a new Random instance. That ruins the generator's statistical properties. Do it once at the beginning of your program.

(Eventually you'll need to consider February 29th too but that's very much a second-order effect).

Upvotes: 3

Related Questions