How to build a random integer array of distinct elements?

Question

I am trying to create a method that fills an array with random integers with no duplicate elements. I'm having trouble making sure each element that is put into the new array is distinct.

Ex. if numOfDigits is 5, then I'd like something like [3][8][2][6][1]. At the moment it either outputs something like [9][0][1][0][0] or infinitely loops.

  private static int[] hiddenSet(int numOfDigits){
    int[] numArray = new int[numOfDigits];
    int temp;
    for (int i = 0; i < numArray.length;  i++){
      do {
        temp = getRandomNum(10);
        numArray[i] = temp;
      } while (isDigitNew(numArray, temp));
      //Each random num must be unique to the array
    }
    return numArray;
  }

  private static boolean isDigitNew(int[] numArray, int index){
    for (int i = 0; i < numArray.length; i++) {
      if (numArray[i] == index) {
        return false;
      }
    }
    return true;
  }

You can step through your program with the debugger to see what's happening. Are you sure that the code you've posted ever completes? — tgdavies, Nov 28 '21 at 00:51
Possible duplicate of [*Generating Unique Random Numbers in Java*](https://stackoverflow.com/q/8115722/230513). — trashgod, Nov 28 '21 at 00:52
One line implementation. `return IntStream.generate(() -> ThreadLocalRandom.current().nextInt(numOfDigits)).distinct().limit(numOfDigits).toArray();` — Elliott Frisch, Nov 28 '21 at 01:07

Locke · Answer 1 · 2021-11-28T01:20:03.813

2

One easy approach is to fill the array with distinct digits then shuffle it.

public static int[] getRandomDistinct(int length) {
    Random rand = new Random();
    int[] array = new int[length];

    // Fill with distinct digits
    for (int i = 0; i < length; i++) {
        array[i] = i;
    }

    // Swap every element with a random index
    for (int i = 0; i < length - 1; i++) {
        int swapWith = i + rand.nextInt(length - i);

        int tmp = array[i];
        array[i] = array[swapWith];
        array[swapWith] = tmp;
    }

    return array;
}

edited Nov 28 '21 at 01:20

answered Nov 28 '21 at 00:51

Locke

7,626
2
21
41

1

Whoops, I meant to use `nextInt(length)` to keep it within the array bounds. – Locke Nov 28 '21 at 00:58
1

I could be wrong, but this looks potentially [biased](https://stackoverflow.com/q/859253/230513). – trashgod Nov 28 '21 at 01:02
1

@trashgod I made a table of possible outcomes depending on the output of `nextInt` and it did come out a tiny bit biased. It probably wouldn't have been noticeable in practice, but for an array of length 4, different variants could vary in probability from 8/4! to 15/4!. I modified the answer and the shuffling should now be completely random since it only selects from the remaining unchosen elements. – Locke Nov 28 '21 at 01:25
I think the maximum value of a random number should be 10 (inclusive or exclusive) that is the argument of `getRandomNum()`. – Nov 28 '21 at 01:50

score 1 · Answer 2 · answered Nov 28 '21 at 01:04

Your algorithm takes quadratic time at best. When the choice of random numbers becomes less looping may take ages. Even infinite might be possible.

Add a positive random number + 1 to the previous generated number. The desired range of numbers needs a bit of care.

At he end shuffle. If you start with a List, you can use Collections. shuffle.

score 0 · Answer 3 · 2021-11-28T02:02:11.187

You can use IntStream like this.

private static int[] hiddenSet(int numOfDigits) {
    return IntStream.iterate(getRandomNum(10), i -> getRandomNum(10))
        .distinct()
        .limit(numOfDigits)
        .toArray();
}

and

public static void main(String[] args) {
    int[] a = hiddenSet(5);
    System.out.println(Arrays.toString(a));
}

output:

[7, 4, 5, 0, 1]

How to build a random integer array of distinct elements?

3 Answers3