Shuffling numbers in a map and selecting one.

Question

I have a group of fixed numbers from 1 to 5. These are added into a Map as follows:

map.put(1, 1);
map.put(2, 2);
map.put(3, 3);
map.put(4, 4);
map.put(5, 5);

From that I randomly take two numbers that I remove from the Map<Integer, Integer> leaving three numbers.

map.remove(Rwiner);
map.remove(Rsec);

This would leave me three numbers like 2,1,4. I want to pick out a random number from that. What should i do?

Answer 1

Are you asking how in Java to select three distinct random integers in the range 1..5?

How about creating a List with the values 1, 2, 3, 4, 5, then calling Collections.shuffle then just looking at the first three elements?

Source code:

import java.util.Collections;
import java.util.Arrays;
import java.util.List;
public class ThreeOfFive {
    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            System.out.println(randomThreeOfFive());
        }
    }

    /**
     * Returns a list of three integers randomly selected from 1, 2, 3, 4, 5.
     */
    public static List<Integer> randomThreeOfFive() {
        List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
        Collections.shuffle(list);
        return list.subList(0, 3);
    }
}

Answer 2

Something like this perhaps:

// Setup
Map<Integer, Integer> map = new HashMap<Integer, Integer>();

map.put(1, 1);
map.put(2, 2);
map.put(3, 3);
map.put(4, 4);
map.put(5, 5);

int Rwiner = 3, Rsec = 5;

map.remove(Rwiner);
map.remove(Rsec);

// Get random entry from current map.
Random rnd = new Random();
int randomIndex = rnd.nextInt(map.size());
int randomKey = new ArrayList<Integer>(map.keySet()).get(randomIndex);
System.out.printf("Random entry: %d -> %d", randomKey, map.get(randomKey));

Answer 3

Uh, from what little I understand, you need to keep removing a number randomly from your map. I think an array is better suited for your task.

Step 1: Convert map into an array. i.e. use values() and toArray().    
Step 2: Use map.size() as the upper bounds on nextInt(int n) on a Random 
        object.    
Step 3: Use the value from step 2 to find the corresponding index of the 
        randomly selected value on the array generated in step 1.

However, each time you remove an object randomly, you will have to repeat these steps, and therefore, keep creating a new array each time (or as aioobe suggested, you will need to keep copying the set values into an arraylist) and this is wasteful. Lets see if we can do this more efficiently only using one array (and not creating a new one each time):

Example:

Array: [1] [2] [3]
Randomly select index 2: [3] [?] [?]
Swap dead index: [x] [2] [1]

Array: [x] [2] [1]
Randomly select index 2: [1] (obv. it doesn't matter if you select index 1)
Swap dead index: [x] [x] [2]

So the above method is more efficient as the array knows that the first k elements are dead. Implementation is as follows:

public static void randArray(int[] arr, int pickHowMany) {
   //error checking
   if(pickHowMany > arr.length())
      return;
   int temp, index;
   Random rand = new Random();
   for (int i = 0; i < pickHowMany; i++){
      index = rand.nextInt(arr.length - i) + i;
      temp = arr[i];
      arr[i] = arr[index];
      arr[index] = temp;
   }
}

So the above method is way more efficient as it works on the same array, rather than creating a new array of arraylist each time. Plus, you can pick multiple numbers by changing the pickHowMany parameter- the method runs in O(n). Do take note that it works on arrays, so all you need to do is convert your map into an array once.

Ray's solution is good too, but it is inefficient if you shuffle each time you want to pick one (i.e. O(n^2)). However, if you shuffle only once, Ray's solution runs at O(n) and you can subsequently pick how many ever numbers you want from the list. So this is again at O(n) for multiple numbers, which is the same complexity as mine although, traversing through a list to remove the first n numbers is far clunkier than selecting the first n numbers of an array.