I need to generate list of random int items without duplicates.
for example: n = 6( 0, 5, 2, 3, 1, 4). I write simple algorithm based on mixing of list (0, 1, 2, ..., n - 1). Can I do it without using random? I think about group theory, but can't imagine solution;
static class RandomIndex {
private final int arr[];
public RandomIndex(int round) {
arr = new int[round];
for (int i = 0; i < round; i++)
arr[i] = i;
Random random = new Random();
for (int i = 0, j, t; i < round; i++) {
j = i + random.nextInt(round - i);
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
public int getValue(int i) {
return arr[i];
}
}
Say a $k$-long list is needed.
(!) Start by generating a random list of $k$ elements, with duplicates, shorten it by deleting the duplicates; being left with a list of length $p$.
Then, iteratively repeat step (!) generate lists of the size $k-p$ from the remaining candidate elements ($k-p$ replaces the $k$ from the previous step).
Iterate until a step where k=p, that is the list is the desired length.
Alternatively, start with picking a random from the list of $n$ options for the first element, from $n-1$ remaining for the second option, from the $n-2$ remaining for the third option, until the $k$-th pick from $(n-k)+1$ remaning options.
Third option
Generate a random integer in the [0,2n-1] range, where $n$ is the number of elements you choose from. Check if the sum of the digits in binary for the random number is k. Repeat until such number is found.
This number is a choice function for the set of candidate elements that picks exactly k elements (those positions for which the binary digit of your number is 1).
You will have to scramble the order of the numbers in the result if the original set of elements to chose from is ordered in some form.