Randomizing a long array with only unique digits

Ramin Amiri Source

I'm trying to make a long array composed of the digits 0 - 9 in a random order, meaning there would be no duplicates of the same digit. I'm a novice coder, and this is what I tried to come up with.

    public static void shuffle() 
{
    long[] rn = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

    Random rand = new Random();

    for (int i = 0; i < 10; i++) {
        int n;
        n = rand.nextInt(10) + 0;

        for (int j = 0; j < 10; j++) 
        {
            if (n != rn[j]) 
            {
               j++; 
            }
            else if (n == rn[j]) 
            {

                n = rand.nextInt(10) + 0;
                if (j > 0) 
                {
                    j--;
                }
            }
        }
        rn[i] = n;
    }

    for (int l = 0; l < 10; l++) 
    {
        System.out.print(rn[l]);
    }
    System.out.println();

}

By my understanding, this shouldn't let any duplicate digits pass, yet it does. Did I do something wrong?

PS: I'm not allowed to use collections or array lists. I'm using the Ready To Program IDE which apparently doesn't support those.

javaarraysfor-looprandom

Answers

answered 3 months ago Boendal #1

So second one. There are many flaws in it.

You should never change your for variable inside of your code only when you really know what you do.

if (n != rn[j]){
    j++; 
}

That is wrong => you will skip a few elements because you already increase the variable in the for loop. So in each iteration you increase it +2.

But because you want to check all other elements from the beginning again when one test failed you have to put in the else part j=-1. Why -1? Because in the last step of the for loop the for loop will increase it by 1 so you will start with 0 again.

j = -1;

When you change the one above so that you don't increase it you will run into a never ending loop. The reason is, that you are prefilling it with zeros. Would you fill it with 10 or some other numbers (not 0-9) it won't happen. So one way is to fill the array with other numbers or only check the first i numbers you have filled with random numbers:

for (int j = 0; j < i; j++) 

In the end this should work:

for (int i = 0; i < 10; i++) {
    int n;
    n = rand.nextInt(10);

    for (int j = 0; j < i; j++) 
    {
        if (n == rn[j]) 
        {

            n = rand.nextInt(10);
            j = -1;
        }
    }
    rn[i] = n;
}

answered 3 months ago MC Emperor #2

You are indeed doing some peculiar things.

  • Changing the loop variable — Most of the time, one should only modify the loop variable (i and j in your case) when some serious magic is needed, otherwise, the loop variable should be left alone.
  • Voodooish + 0 — Adding 0 to a value is pointless.

Regarding your shuffle method, I'm proposing a whole other approach. You have a loop within a loop, so the execution time will exponentially increase when the array is larger.

Instead, one could also select a random index from the source array, and then fill the next position of the new array with that value. Of course, in order to avoid a value from the source array to be picked twice, we will swap that value with the value on the last position of the source array and decrement its size.

index | 0 | 1 | 2 | 3 | 4  |
value | 2 | 3 | 5 | 7 | 11 |
arraySize: 5

Step 1. Pick random index, where index is less than arraySize
(in this example index 1 has been picked)

index | 0 | 1 | 2 | 3 |  4 |
value | 2 | 3 | 5 | 7 | 11 |
arraySize: 5
pickedIndex: 1

Step 2. Swap value at pickedIndex with value at index arraySize − 1

index | 0 |  1 | 2 | 3 | 4 |
value | 2 | 11 | 5 | 7 | 3 |
arraySize: 5

Step 3. Decrease array size, so the value previously on the picked
position won't be picked again

index | 0 |  1 | 2 | 3 |
value | 2 | 11 | 5 | 7 |
array size: 4

The code looks like this:

private static int[] shuffle(int[] array) {
    int[] availableNumbers = new int[array.length];
    int availableNumbersLength = availableNumbers.length;
    System.arraycopy(array, 0, availableNumbers, 0, array.length);
    int[] shuffledArray = new int[availableNumbers.length];

    Random r = new Random();
    for (int i = 0; i < availableNumbers.length; i++) {
        int index = r.nextInt(availableNumbersLength);
        shuffledArray[i] = availableNumbers[index];
        availableNumbers[index] = availableNumbers[availableNumbersLength - 1];
        availableNumbersLength--;
    }
    return shuffledArray;
}

Note that I copied the input array so that the source array is left unchanged and a new array containing the elements in a random order, is returned. You could also, of course, shuffle the original array.

answered 3 months ago Alex Savitsky #3

The brute-force implementation:

public static void shuffle() {
    int[] a = new int[10];
    Random rand = new Random();
    int count = 0;
    while (count != 10) {
        int n = rand.nextInt(10);
        boolean found = false;
        for (int i = 0; i != count; i++) {
            if (a[i] == n) {
                found = true;
                break;
            }
        }
        if (!found) {
            a[count] = n;
            count++;
        }
    }
    for (int i : a) {
        System.out.println(i);
    }
}

Basically, maintain a count of numbers already generated, and verify each new one against the already generated numbers (in the range of 0 .. count)

Here's another implementation that might be faster if your alphabet is large (e.g., if you generate unique combination of ~10M tokens rather than 10):

public static void shuffleO1() {
    int[] a = new int[10];
    for (int i = 0; i != a.length; i++)
        a[i] = -1;
    Random rand = new Random();
    for (int i = 0; i != 10; i++) {
        int n;
        do {
            n = rand.nextInt(10);
        } while (a[n] != -1);
        a[n] = i;
    }
    for (int i : a) {
        System.out.println(i);
    }
}

Here, the basic idea is that you iterate over your alphabet (0-9 in our case) and try to find a random place for each token, re-randomizing the index until you find a non-filled position. You pre-fill the result array with -1 first, to tell the generated zero from the one placed there by the array initialization

comments powered by Disqus