CODEWITHSUNDEEP
arrayssortingrandom
Lincoln
Lincoln

Reputation: 11

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

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.

Upvotes: 1

Views: 3505

Answers (5)

ShadowRanger
ShadowRanger

Reputation: 155363

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.

Upvotes: 0

Valdio
Valdio

Reputation: 109

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

Upvotes: 0

Kiraa
Kiraa

Reputation: 529

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.

Upvotes: 1

Kusalananda
Kusalananda

Reputation: 15613

  1. generate a random index into the array.

  2. repeat until it's different from the last index used.

  3. pull the value corresponding to that index out of the array.

  4. repeat from beginning until you have as many numbers as you need.

Upvotes: 1

Erik
Erik

Reputation: 3636

  • 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

Upvotes: 0

Related Questions