CODEWITHSUNDEEP
java
Secret
Secret

Reputation: 3348

Getting n random elements in array

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?

Upvotes: 0

Views: 540

Answers (6)

avanderw
avanderw

Reputation: 675

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.

Upvotes: 0

user3094317
user3094317

Reputation: 15

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

Upvotes: 0

HybrisHelp
HybrisHelp

Reputation: 5810

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.
  }

Upvotes: 1

Burkhard
Burkhard

Reputation: 14738

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;
}

Upvotes: 0

kai
kai

Reputation: 6887

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]); 
       }

Upvotes: 0

Rahul
Rahul

Reputation: 45060

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
}

Upvotes: 1

Related Questions