CODEWITHSUNDEEP
javaarraysrandom
Mavix
Mavix

Reputation: 181

How can I avoid duplicates when generating a random list of pairs of numbers?

I have the following code to set 10 random values to true in a boolean[][]:

    bommaker = new boolean[10][10];
    int a = 0;
    int b = 0;

    for (int i=0; i<=9; i++) {          

        a = randomizer.nextInt(9);
        b = randomizer.nextInt(9);
        bommaker[a][b] = true; 
    }

However, with this code, it is possible to have the same value generated, and therefore have less then 10 values set to random. I need to build in a checker, if the value isn't already taken. And if it is already taken, then it needs to redo the randomizing. But I have no idea how to do that. Can someone help me?

Upvotes: 1

Views: 1301

Answers (2)

TacticalCoder
TacticalCoder

Reputation: 6335

You're problem is similar to drawing cards at random from a deck if I'm not mistaken...

But first... The following:

randomizer.nextInt(9)

will not do what you want because it shall return an integer between [0..8] included (instead of [0..9]).

Here's Jeff's take on the subject of shuffling:

http://www.codinghorror.com/blog/2007/12/shuffling.html

To pick x spot at random, you could shuffle your 100 spot and keep the first 10 spots.

Now of course seen that you'll have only 10% of all the spots taken, simply retrying if a spot is already taken is going to work too in reasonable time.

But if you were to pick, say, 50 spots out of 100, then shuffling a list from [0..99] and keeping the 50 first value would be best.

For example here's how you could code it in Java (now if speed is an issue you'd use an array of primitives and a shuffle on the primitives array):

    List<Integer> l = new ArrayList<Integer>();
    for (int i = 0; i < 100; i++) {
        l.add(i);
    }
    Collections.shuffle(l);
    for (int i = 0; i < n; i++) {
        a[l.get(i)/10][l.get(i)%10] = true;
    }

Upvotes: 4

sverre
sverre

Reputation: 6919

simplest solution, not the best:

for (int i=0; i<=9; i++) {          
    do {
        a = randomizer.nextInt(10);
        b = randomizer.nextInt(10);
    } while (bommaker[a][b]);

    bommaker[a][b] = true; 
}

Upvotes: 6

Related Questions