The Random
class has nextInt()
function that takes an upper bound
and returns a random number from 0
to upper bound
.
Keep upper bound
as the length of the array
, Generate the random number between 0
and upper bound
. swap the random Number Positioned element with the end of the array, decrement upper bound
.
The logic is also known as the Fisher-Yates
shuffle algorithm.
package org.wesome.dsalgo;
import java.util.Arrays;
import java.util.Random;
class RandomWithoutRepetitions {
public static void randomWithoutRepetitions(int[] arr) {
System.out.println("arr = " + Arrays.toString(arr));
int bound = arr.length - 1;
int randomNumber;
Random random = new Random();
for (int i = 0; i <= arr.length - 1; i++) {
randomNumber = random.nextInt(bound + 1);
System.out.println(i + " randomNumber = " + arr[randomNumber]);
bound = swapPosition(arr, randomNumber, bound);
}
}
private static int swapPosition(int[] arr, int randomNumber, int max) {
arr[randomNumber] = arr[randomNumber] ^ arr[max];
arr[max] = arr[randomNumber] ^ arr[max];
arr[randomNumber] = arr[randomNumber] ^ arr[max];
max--;
return max;
}
}
package org.wesome.dsalgo;
import org.junit.jupiter.api.Test;
import static org.wesome.dsalgo.RandomWithoutRepetitions.randomWithoutRepetitions;
public class RandomWithoutRepetitionsTest {
@Test
void RandomWithoutRepetitionsTest1() {
randomWithoutRepetitions(new int[]{10, 9, 8, 7, 6});
}
@Test
void RandomWithoutRepetitionsTest2() {
randomWithoutRepetitions(new int[]{1});
}
@Test
void RandomWithoutRepetitionsTest3() {
randomWithoutRepetitions(new int[]{});
}
}