CODEWITHSUNDEEP
java
Talen Kylon
Talen Kylon

Reputation: 1968

Generate two random integers and remove them from being generated again

I have an ArrayList of Car objects, and I want to randomly select two of them and compare them. Once we compare them, I want the inferior car to be "removed" from being randomly picked again. I don't think we can stop specific numbers from being generated, so I've thought of some other ideas.

Here are some things I've been thinking:

Idea 1:
Include a "seen" attribute for each Car, set to false.
Generate two random integers from 0 to size of Car List.
Check to make sure two indexes are not seen.
Check to make sure that two integers are not the same, if they are, regenerate and repeat.
Grab cars using the two indexes generated. 
If not seen, compare and flag the inferior as seen. 
If seen, store that cars index in a seenIndex array.

Idea 2:
Create a copy (would a deep copy be required here, im thinking no?) of the list of Cars.
Generate two random numbers, confirm they're not the same. 
Compare cars, remove the inferior car from the copyList.
Repeat.

I'm leaning towards idea 2, but I'd love to hear of a more elegant solution if one exists.

Upvotes: 0

Views: 57

Answers (3)

MercyBeaucou
MercyBeaucou

Reputation: 268

As others have said, idea #1, although it would work, isn't viable with lists of cars of a decent size.

I would go with option 2

One thing about confirming that the 2 random #s are not the same though - I would advise you not to create another Random number, but rather to do this:

Random rnd = new Random()

int rand1 = rnd.nextInt(copyList.size() - 1); 
int rand2 = rnd.nextInt(copyList.size() - 2);

if(rand2 >= rand1) rand2++;

This avoids creating a random number that is possibly the same as the one you had to replace, and would make your program a lot faster.

However, if you are just trying to figure out which car is better, you could iterate through an array (or list) of Car classes, comparing each one to the current best (where cars is an array of cars and getPoints() returns how good the car is):

int bestIndex = 0;

// Loop starts at 1 b/c we don't need to compare index 0 w/ 0
// i.e. # of comparisons is 1 minus the # of Cars
for(int i = 1; i < cars.length - 1; i++){ 

    if(cars[i].getPoints() > cars[bestIndex].getPoints()){
        bestIndex = i;
    }

}

This will preserve the array and efficiently find the best car. This of course can be modified for a list.

Upvotes: 2

Matt C
Matt C

Reputation: 4555

Your idea 2 is a very straightforward approach that I would recommend.

The only thing to change is that the copy arraylist does not need to be a deep copy. This is because with a shallow copy (which is less expensive), removing an item from one list has no affect on the other list.

You definitely don't want to keep track of what indeces have been used, like the other answer suggests.
This math post explains why the other answer is a bad idea. The math doesn't directly translate over to this example because there is more than one target number (except for the last iteration), but there is still a large expected number of tries before a hit, especially as you start with larger lists of cars.

Upvotes: 1

pascalnouma
pascalnouma

Reputation: 31

Alternatively, you can store the randomly generated number(s) in an arraylist, then every-time you generate new random number you can first check the array, if not contains you can select it. You can do something like that : 

public int generateRandomNumber(int start, int end, ArrayList<Integer> excludedNumbers) {
    Random rand = new Random();
    int range = end - start + 1;
    int random = rand.nextInt(range) + 1;
    while(excludedNumbers.contains(random)) { 
        random = rand.nextInt(range) + 1;
    }

    return random;
}

Upvotes: 0

Related Questions