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?

Solution 1

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

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

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

Solution 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.

Solution 4

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

View more solutions

Comments

[Ivaylo Strandjev]

I believe he relies on the fact that exclude is sorted.

[qben]

@user2081119 I suggest you to take a look at my solution. There are some remarks which would be helpful I think.