I want to get n unique random elements from my array.
For example:
if n = 4;
I want to randomly get
array[0], array[3], array[7], array[2]
The problem is getting a random integer will lead to collisions easily (psuedocode):
for n times
{
r = generateRandomInteger within n-1
list.push(array[r]); //array[r] can be the same.
}
collisions abound, especially on small arrays.
What's a particularly elegant way to solve this?
You can use a Set instead of a List which will eliminate the duplicates. Accordingly you'll need to change your loop condition as well. Something like this
while set.size() is less than n
{
r = generateRandomInteger within n-1
set.add(array[r]); //if its the same, it won't be added to the set and the size won't increase
}
You can do this two way : i suggest you to use first one .
First by using SET :
for n times
{
r = generateRandomInteger within n-1
// you can use SET instead of LIST cause SET not allow duplication.
set.push(array[r]); //array[r] can be the same.
}
Second by using LIST :
for n times
{
r = generateRandomInteger within n-1
if(!list.contains(array[r]))
list.push(array[r]); //array[r] can be the same.
}
You can add all random ints to a list and generate a new random, till the list doesnt contains this random int. Thats not the best performance, but it works.
List<Integer> randoms = new ArrayList<Integer>()
for(int i=0; i<n;i++){
while(randoms.contains(r)) {
r = Random.nextInt(array.length-1);
}
randoms.add(r);
list.push(array[r]);
}
Using a Set is probably the best thing to do.
If you want unique elements from array (i.e. the values of array[]) then use R.J's solution. If you want unique indices:
while set.size() is less than n
{
r = generateRandomInteger within n-1
set.add(r);
}
foreach(r: set)
{
list.add(array[r]);
}
Be carefull if you want more elements then the length of the array, since you will get an infinite loop:
if(n>array.length)
{
print("Cannot get more then ... elements!");
return null;
}
Set was meant for such purposes.int n = 4;
for (int i = 0; i < n; i++)
{
int index = RandomBetweenInclusive(i, array.length() - 1); //made up function
int temp = array[i];
array[i] = array[index];
array[index] = array[i];
}
//array values between indices 0 and n-1 will be random and unique values of array
What I usually do in this scenario is push all the items I want to select-from into a collection
var selectFrom = original.clone; // or build array
var selected = new collection;
Then I go about removing random elements in the selectFrom collection
for (i = 0; i < toSelect; i++)
{
var rndItem = selectFrom[ rand() * selectFrom.length ];
selected.add(rndItem);
selectFrom.remove(rndItem);
}
This way I select randomly from what remains and do not have to worry about clashes in random numbers / indexs.
