Random number only once

[Gaz1634]

What is the best way to pick random elements of an array, but only allow each element to be picked once? The elements are instances of a custom class.

Any help is greatly appreciated

 

[progbass8]

you could give your custom class a boolean value to track wether it was picked or not
then in the random method you pick a random number:
if it has been picked use recursion to invoke the method again
if not you return the result.

i think that would work anyway

 

[kaht]

What I like to do (assuming your array isn't HUGE) is create a copy of the array and then do random swaps of the elements in the array. You'll obviously wanna do more swaps the larger your array is. Afterwards, you can just use a for loop to print the elements of the array copy (which should be all mixed up at that point)

-kaht

 

[hologram]

You can pick a random number from the array.
Then you swap the last element of the array with the picked element.
Then you pick a random number from the array (but pretending it is 1 element shorter) and swap it with the last but one.
You can repeat these steps until there are no more elements left.

 

[kaht]

hologram's solution will work but take note that it will destroy your original array order

-kaht

 

[byam]

One way to do it would be to use minimal perfect hash function, mapping n unique keys to n items. This way you don't need to copy the array or changing the order of the original array.

say you have an array to be randomly pick:

// create a hashing array
int n = array.length;

int[] x = new int[n];
Random rand = new Random();

for (int i=0; i<n; i++)
   x[i] = i;
 
  // changing k change the mapping
   int k = rand.nextInt(n/2);  
   int s;
   for (int i=0; i<3; i++) {
      for (int j=0; j<n; j++) {
         s = x[i];
         k = (k+s) % n;
         x[i] = x[k];
         x[k] = s;
     }
  }
}
// now use the hashing array to get item from the array in shuffled order

for (int i=0; i<n; i++) {
   array[x[i]];
}

However, the above hash function (Pearson's hash) is only good if n is large.

Number of elements Chance that no mimimal perfect hash exists

            chance that the hash is not perfect
n           (not one to one mapping)
---         -------------------------------
2           .25  
3           .2213773  
4           .0941787  
5           .0091061  
6           .0000137  
7           .0000000000000003

So if n is greater than 5, the chances of collision is mininal.