How do I generate random numbers from an array without repetition?

Question

I know similar question have been asked before but bear with me.

I have an array:

int [] arr = {1,2,3,4,5,6,7,8,9};

I want numbers to be generated randomly 10 times. Something like this:

4,6,8,2,4,9,3,8,7

Although some numbers are repeated, no number is generated more than once in a row. So not like this:

7,3,1,8,8,2,4,9,5,6

As you can see, the number 8 was repeated immediately after it was generated. This is not the desired effect.

So basically, I'm ok with a number being repeated as long as it doesn't appear more than once in a row.

Show us some code. What have you tried, and what problems did you encounter? — Franko Leon Tokalić, Jul 28 '16 at 16:08
This problem is called "random sampling without replacement." It is well studied. — AShelly, Jul 28 '16 at 17:18
@AShelly: Except that isn't the problem here. The question you say is a duplicate wants to _never_ repeat a number. The OP's problem is to just avoid repeating a given number twice in a row, but you could legally produce `8, 4, 8`. I wouldn't be surprised if this was a duplicate, but it's not the one you linked when closing as a duplicate. — ShadowRanger, Jul 28 '16 at 20:59
@kiraa's answer is the correct solution with deterministic time. — AShelly, Jul 28 '16 at 21:20

score 1 · Answer 1 · answered Jul 28 '16 at 16:03

1

Generate a random number.
Compare it to the last number you generated
If it is the same; discard it
If it is different, add it to the array
Return to step 1 until you have enough numbers

answered Jul 28 '16 at 16:03

Erik

3,598
14
29

score 1 · Answer 2 · answered Jul 28 '16 at 16:05

1

generate a random index into the array.
repeat until it's different from the last index used.
pull the value corresponding to that index out of the array.
repeat from beginning until you have as many numbers as you need.

answered Jul 28 '16 at 16:05

Kusalananda

14,885
3
41
52

score 1 · Answer 3 · answered Jul 28 '16 at 16:18

While the answers posted are not bad and would work well, someone might be not pleased with the solution as it is possible (tough incredibly unlikely) for it to hang if you generate long enough sequence of same numbers.

Algorithm that deals with this "problem", while preserving distribution of numbers would be:

Pick a random number from the original array, let's call it n, and output it.
Make array of all elements but n
Generate random index from the shorter array. Swap the element on the index with n. Output n.
Repeat last step until enough numbers is outputed.

You can skip the copy in step 2 by swapping item `n` with the last element, and then selecting an element from the range `[0..size-1)` — AShelly, Jul 28 '16 at 21:25

score 0 · Answer 4 · answered Jul 28 '16 at 17:15

    int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int[] result = new int[10];
    int previousChoice = -1;

    int i = 0;
    while (i < 10) {
        int randomIndex = (int) (Math.random() * arr.length);
        if (arr[randomIndex] != previousChoice) {
            result[i] = arr[randomIndex];
            i++;
        }
    }

score 0 · Answer 5 · edited May 23 '17 at 12:32

The solutions given so far all involve non-constant work per generation; if you repeatedly generate indices and test for repetition, you could conceivably generate the same index many times before finally getting a new index. (An exception is Kiraa's answer, but that one involves high constant overhead to make copies of partial arrays)

The best solution here (assuming you want unique indices, not unique values, and/or that the source array has unique values) is to cycle the indices so you always generate a new index in (low) constant time.

Basically, you'd have a with loop like this (using Python for language mostly for brevity):

# randrange(x, y) generates an int in range x to y-1 inclusive
from random import randrange

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
result = []
selectidx = 0
randstart = 0

for _ in range(10):  # Runs loop body 10 times
    # Generate offset from last selected index (randstart is initially 0
    # allowing any index to be selected; on subsequent loops, it's 1, preventing
    # repeated selection of last index
    offset = randrange(randstart, len(arr))
    randstart = 1

    # Add offset to last selected index and wrap so we cycle around the array
    selectidx = (selectidx + offset) % len(arr)

    # Append element at newly selected index
    result.append(arr[selectidx])

This way, each generation step is guaranteed to require no more than one new random number, with the only constant additional work being a single addition and remainder operation.

How do I generate random numbers from an array without repetition?

5 Answers5