Generate random numbers except certain values

问题:

I want to generate random numbers, but don't want them to be from excludeRows array. Here is my code.

public int generateRandom(int start, int end, ArrayList<Integer> excludeRows) {
    Random rand = new Random();
    int range = end - start +1 - excludeRows.size();
    int random = rand.nextInt(range) + 1;

    for(int i = 0; i < exclude.size(); i++) {
        if(excludeRows.get(i) > random) {
            return random;
        }
      random++;
    }

    return random;
}

I use this function in a while loop, and during each iteration I add a new value to excludeRows. Sometimes it returns numbers that belong to excludeRows. What's the problem?

回答1:

if(!exclude.contains(random))
    return random;

Try this every time it will return the value that is not in exclude.

回答2:

I think there are some mistakes.

1) Range should be end - start + 1, because this is the range wanted.
2) If you really want random numbers (as "random" as possible on computers) then you shouldn't just get the next available number. Because in this case your random number will bear the characteristics of excluded numbers density/frequency.

public int generateRandom(int start, int end, ArrayList<Integer> excludeRows) {
    Random rand = new Random();
    int range = end - start + 1;
    int random;

    boolean success = false;
    while(!success) {
        random = rand.nextInt(range) + 1;
        for(Integer i: excludeRows) {
            if(i == random) {
                break;
            } else if (i > random) {
                success = true;
                break;
            }
        }
    }
    return random;
}

UPDATE

With Achintya Jha's answer my code could be improved (but note there are some remarks as well):

public int generateRandom(int start, int end, ArrayList<Integer> excludeRows) {
    Random rand = new Random();
    int range = end - start + 1;

    int random = rand.nextInt(range) + 1;
    while(excludeRows.contains(random)) {
        random = rand.nextInt(range) + 1;
    }

    return random;
}

回答3:

You check:

for(int i = 0; i < exclude.size(); i++) {
    if(exclude.get(i) > random) {
        return random;
    }

and if only the first is larger, you'll return the value. Are you sure exclude is sorted?

You can use if(exclude.contains(random )) or the following algorithm:

if (end-start) is a reasonable number, and you need almost all values you can create a list of all acceptable numbers and use random on this list size and choose the random value as an index. then remove the unwanted number from the list and get another random index.

回答4:

Actually, we do not need to use contains(random) with a while loop.

To simplify the question, let's see what happens if we only have one excluding value. We can split the result to 2 parts. Then the number of possible values is range-1. If the random number is less than the excluded value, just return it. Otherwise, we could add 1.

For multiple excluding values, We can split the result set into size+1 parts, where size means the number of excluding values. Then the number of possible values is range-size. Then we sort excluding values in ascending order. If random number is less than the excluding value minus i, then we just return the random number add i, where i is the index of the the excluding value.

public int generateRandomNumberWithExcepts(int start, int end, List<Integer> excepts) {
    int size = excepts.size();
    int range = end - start + 1 - size;
    int randNum = random.nextInt(range) + start;
    excepts.sort(null); // sort excluding values in ascending order
    int i=0;
    for(int except : excepts) {
        if(randNum < except-i){
            return randNum + i;
        }
        i++;
    }
    return randNum + i;
}