randomly pick 12 items with no duplicates

[Santh Narayanan]

Hi,
I have a new requirement in my project where I have to randomly pickup 12 unique Social security numbers (SSN) form a list of 160 SSN stored in out UDB database. My question is how do I exclude duplicates and still get 12 SSN’s within the given range (160). I would really appreciate if any body can help me.
Thanks,
santh

[Michael Morris]

Use a Set. A set does not allow duplicates. Generate your random SS numbers put them in the Set and when the size() method returns 12 bugout of the loop:

    Set randSS = new HashSet();
    while(randSS.size() != 12) {
        String rand = getRandSS();
        randSS.add(rand);
    }

Of course your will no doubt need to change the line String rand = getRandSS();.
Michael Morris

[Santh Narayanan]

Thank you Michael

[Peter den Haan]

A totally different approach would be to read your numbers (which, presumably, are guaranteed to be unique by a constraint in the database or somesuch) into a List such as an ArrayList, call java.util.Collections.shuffle(), and then simply use the first 12 numbers from the list or however many you need.
If you're really paranoid and want a totally unpredictable source of randomness, instantiate a java.security.SecureRandom and pass that into your shuffle call.
- Peter

[Layne Lund]

I think the later method would be preferred. For one, the random number generator cannot gurantee that the SSN returned actually exists within the given set of SSNs. Also, the random number generator could (theoretically) generate the same set of numbers indefinitely before it generates all 12 that you need.

[Michael Morris]

... generate the same set of numbers indefinitely before it generates all 12 that you need.

And I could win the lottery 12 times in a row. :roll:

[Layne Lund]

Originally posted by Michael Morris:

And I could win the lottery 12 times in a row. :roll:

Heh...Well, theoretically, you COULD. Granted, the probability is small, but there is still the possibility.
[ April 10, 2003: Message edited by: Layne Lund ]

[Jim Yingst]

I think the later method would be preferred. For one, the random number generator cannot gurantee that the SSN returned actually exists within the given set of SSNs.
Depends how you generate them. You've got a list of 160 or so valid numbers - choose an index from 0 to 159, and use the SSN for that index.
Also, the random number generator could (theoretically) generate the same set of numbers indefinitely before it generates all 12 that you need.
Well, you can avoid this with suitable modifications. In fact, if the original list has nothing but unique values in the first place, you can avoid the need for a HashSet entirely. Here - assume that all 160 possible SSNs have been leaded into a List called availableSSNs:

    for (int i = 0; i < 12; i++)
    {
        int index = (int) (Math.random() * availableSSNs.length());
        String ssn = availableSSNs.remove(index);
        doSomethingWith(ssn);
    }

By removing each SSN as it's chosen, you ensure that only 12 random choices will be necessary.

[Santh Narayanan]

Jim,
By removing each SSN as it's chosen, you ensure that only 12 random choices will be necessary.
Will all 12 be unique in this case.
Thanks
Santh

[Stan James]

Just another vote for shuffle(). It scrambles a collection into random order so the first 12 you pick will be random selections. I think I invented this algorithm independently 20 years ago when somebody asked me for something to pick lottery numbers.

[Jim Yingst]

Will all 12 be unique in this case.
Assuming (as stated) that the original list of 160 SSNs did not contain any duplicates, then yes. This is the same assumtion Peter makes.
Just another vote for shuffle().
Yeah. I think that the shuffle() approach makes more sense the larger the number of SSNs you need to choose - it's going to spend time shuffling the entire list, so there's a certain amount of waste for the unused numbers. Conversely my algorithm is not as fast if you want to pick a lot of numbers, but works well for a small set. No idea where the break-even point is; you'd have to test. Note also that my algorithm could use either a LinkedList or ArrayList; I'm not sure which one will be faster for this particular problem.