Generate random numbers except certain values

Question

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

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

    for(int i = 0; i < exclude.size(); i++) {
        if(exclude.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 exclude. Sometimes it returns numbers that belong to exclude. What's the problem?

In this function you don't add numbers to `excludeRows`. So in my solution I don't do that, either. Should I supplement it? — qben, Feb 18 '13 at 12:33

qben · Answer 1 · 2013-02-18T12:52:16.977

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

score 6 · Accepted Answer · answered Feb 18 '13 at 12:21

6

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

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

answered Feb 18 '13 at 12:21

Achintya Jha

12,735
2
27
39

@user2081119 I suggest you to take a look at my solution. There are some remarks which would be helpful I think. – qben Feb 18 '13 at 12:38

BobTheBuilder · Answer 3 · 2013-02-18T12:24:23.813

2

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.

edited Feb 18 '13 at 12:24

answered Feb 18 '13 at 12:13

BobTheBuilder

18,858
6
40
61

2

I believe he relies on the fact that exclude is sorted. – Ivaylo Strandjev Feb 18 '13 at 12:13

score 1 · Answer 4 · answered Nov 15 '19 at 20:11

this worked for me:

    public int randomInt(int start, int end, int... exception) {
        int result = -1;
        Random rand = new Random();
        int range = end - start + 1;
        boolean equals = true;

        while(equals) {
            result = rand.nextInt(range);
            boolean differentOfAll = true;
            for(int i : exception) {
                if(result==i) {
                    differentOfAll = false;
                    break;
                }
            }
            if(differentOfAll) {
                equals = false;
            }
        }

        return result;
    }

score -1 · Answer 5 · answered Nov 10 '17 at 23:18

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

Generate random numbers except certain values

5 Answers5

Linked