Java Arrays without duplicates using only fundamental techniques

Question

I'm trying to generate an array with 10 random numbers between 0 and 20 (those included) without duplicates using only fundamental technics such as ifs, fors and do..while (therefore I can't use shuffle and basically any shortcut). I´ve already tried "everything" but without success...

Answer 1

I am assuming you are doing this as an exercise to sharpen your coding skills. Otherwise, it does not make sense to restrict yourself to "fundamental techniques".

Also, this code does generate the desired result, so I assume you want to hear what someone with more coding experience would do differently. The code review stack exchange might be a better place for this kind of request.

Algorithm-wise:

• There is no need to recreate the entire array when you find a duplicate. Just re-create this one cell.

• I would create a boolean array used with length 20. When you place a random number r in your result array, set used[r] = true. Now, you can check whether a number is in the array already with a simple check of used[r]. If it is true, you need to create another number. You could do this with a bitset (In reality, I would just use a Set, as Arvid did, or shuffle a list).

Coding style:

• There is a class Random, with a function nextInt(). I would prefer

  Random r = new Random(); r.nextInt(21)

over your solution, as it is more obvious what is going on. You need only one Random-Object, so the line with the new-statement appears just once in your final program. Arvind did this in his answer.

• Do not call the variable "list1". First, it is an array, not a list. So "array1" would be better. Second, this name is not going to tell you anything about the variable. Use a name which describes what the variable is used for. e.g "result" or "random_numbers".

• Same goes for "result". This is not your result. "hasDuplicates" would be a better name.

Answer 2

Use a Set as a Set stores only unique values. Any duplicate value will be discarded at the time of addition.

import java.util.HashSet;
import java.util.Random;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<Integer> set = new HashSet<Integer>();
        Random random = new Random();
        while (set.size() != 10) {
            set.add(random.nextInt(21));
        }
        System.out.println(set);
    }
}

A sample run:

[0, 1, 18, 2, 3, 5, 6, 7, 8, 15]

Alternatively,

import java.util.Arrays;
import java.util.Random;

public class Main {
    public static void main(String[] args) {
        Random random = new Random();
        final int SIZE = 10;
        int[] arr = new int[SIZE];
        int count = 0, n, i;
        while (count != SIZE) {
            // Generate a random number from 1 to 20
            n = random.nextInt(20) + 1; // Alternatively, n = (int) (Math.random() * 20) + 1;

            // Check if n already exists in the array
            for (i = 0; i < SIZE; i++) {
                if (n == arr[i]) {
                    break;
                }
            }

            if (i == SIZE) { // i.e. if the loop terminated without a match
                arr[count++] = n;
            }
        }
        arr[random.nextInt(SIZE)] = 0;// Replace one of the numbers with 0
        System.out.println(Arrays.toString(arr));
    }
}

A sample run:

[7, 11, 10, 14, 1, 15, 21, 5, 6, 0]

Answer 3

If you don't want to use any collections then you need to implement the shuffle function by yourself. After that, you can add numbers from the range to the array and pass it to your shuffle function.

Also, check the following discussion

Answer 4

Here's a simple technique:

for (int a = 0, picked = 0; a < 21 && picked < 10; ++a) {
  if (Math.random()*(21 - a) < (10-picked)) {
  // Or: if (random.nextInt(21 - a) < 10 - picked) {
    arr[picked++] = a;
  }
}

Because of the way it is constructed, it also guarantees not to generate duplicates.

This picks 10 numbers with equal probability (the maths to prove that is reasonably easy to derive using basic probability). If you present this as an answer to whatever homework this is, I would suggest you should be prepared in case you are challenged on its mathematical basis.