permute data for a HashMap in Java

Question

hi

i have a linkedhashmap and i need to permute (change the key of the values) between 2 random values

example :

key 1 value 123 key 2 value 456 key 3 value 789

after random permutation of 2 values

key 1 value 123 key 2 value 789 key 3 value 456

so here I permuted values between key 2 and key 3

thank you;

sample of the code of my map :

    Map map = new LinkedHashMap();
        map =myMap.getLinkedHashMap();

       Set key = map.keySet();

   for(Iterator it = cles.iterator(); it.hasNext();)
    {
        Integer cle =  it.next(); 
        ArrayList values = (ArrayList)map.get(cle);//an arrayList of integers

        int i = 0;
        while(i < values.size())
        {
            //i donno what to do here
            i++;
        }
    }

Answer 1

First, you should use generic collections:

Map<Integer, List<Integer>> map = new LinkedHashMap<Integer, List<Integer>>();

Since this looks like homework, I try to give hints to help you forward, rather than a full solution. StackOverflow is not supposed to write your homework for you :-)

You need the keys of the two elements to swap. Once you have that, you just need to get the values corresponding to the given keys and swap them between the two keys. Then add the random key generation - improving on @Eyal's generic solution:

  class MapSwapper1 {
    private static Random rnd = new Random();
    private static K[] nullArray = new K[0];

    public static <K,V> void swapTwoRandomValues(Map<K,V> map){
      if (map.size() <= 1)
        throw new IllegalArgumentException("Not enough items");

      //Choose 2 random positions pos1<pos2
      int pos1 = 0, pos2 = 0;
      while (pos1 == pos2) {
        pos1 = rnd.nextInt(map.size());
        pos2 = rnd.nextInt(map.size());
      }
      // Get the keys into an indexable array
      K[] keys = map.keySet().toArray(nullArray);

      swap(map, keys[pos1], keys[pos2]);
    }

    private static void <K,V> swap(Map<K, V> map, K key1, K key2) {
      V tmp = map.get(key1);
      map.put(key1, map.get(key2));
      map.put(key2, tmp);
    }
  }

I think this solution may be faster than his even as it is. However, if you swap values within the same map many times without changing the map otherwise (i.e. no keys are added, removed or changed in the map), you can further optimize the solution by reusing the keys array between subsequent swap calls:

  class MapSwapper2<K, V> {
    private Random rnd = new Random();
    private Map<K,V> map;
    private K[] keys;

    public MapSwapper2(Map<K, V> map) {
      resetKeys();
      this.map = map;
    }

    public void resetKeys() {
      if (map.size() <= 1)
        throw new IllegalArgumentException("Not enough items");
      keys = map.keySet().toArray(new K[0]);
    }

    public void swapTwoRandomValues() {
      if (map.size() != keys.length)
        resetKeys();

      //Choose 2 random positions pos1<pos2
      int pos1 = 0, pos2 = 0;
      while (pos1 == pos2) {
        pos1 = rnd.nextInt(map.size());
        pos2 = rnd.nextInt(map.size());
      }
      swap(map, keys[pos1], keys[pos2]);
    }

    private void swap(K key1, K key2) {
      V tmp = map.get(key1);
      map.put(key1, map.get(key2));
      map.put(key2, tmp);
    }
  }

As you see, MapSwapper2 objects are associated with a specific map instance, whose elements they can repeatedly swap. The resetKeys method should be called if the map keys have changed. The swapper can detect if the size of the map has changed, but not if e.g. a key has been removed and another key added.

Answer 2

Since this is not homework, here is my solution. The swapping itself is efficient, but the random sampling of 2 items can be improved :)

private static Random rnd = new Random();
...
public static <K,V> void swapTwoRandomValues(Map<K,V> map){
    if (map.size() <= 1)
        throw new IllegalArgumentException("Not enough items");

    //Choose 2 random positions pos1<pos2
    int pos1 = 0, pos2 = 0;
    while (pos1 == pos2){
        pos1 = rnd.nextInt(map.size());
        pos2 = rnd.nextInt(map.size());
    }       
    if (pos1 > pos2){
        int aux = pos1;
        pos1 = pos2;
        pos2 = aux;
    }

    //Fetch the entries
    Iterator<Map.Entry<K, V>> it = map.entrySet().iterator();
    Map.Entry<K, V> entry1 = null;
    for(int i=0;i <= pos1;i++)
        entry1 = it.next();
    Map.Entry<K, V> entry2 = null;
    for(int i = pos1;i < pos2;i++)
        entry2 = it.next();

    //Swap values
    V tmpValue = entry1.getValue();
    entry1.setValue(entry2.getValue());
    entry2.setValue(tmpValue);
}

Answer 3

Noticed a few people typed up something already, but this is fairly complete, it's not the most efficient code but it will help you on your way and will put the values back in the map.

    Map<Integer, Integer> map = new LinkedHashMap<Integer, Integer>();
    map.put(1, 123);
    map.put(2, 456);
    map.put(3, 789);

    for (Entry<Integer, Integer> entry : map.entrySet())
        System.out.println("old key: " + entry.getKey() + " and value: " + entry.getValue());

    List<Integer> values = new ArrayList<Integer>(map.values());
    Collections.shuffle(values);

    int i = 0;
    for (Entry<Integer, Integer> entry : map.entrySet())
    {
        map.put(entry.getKey(), values.get(i));
        i++;
    }

    for (Entry<Integer, Integer> entry : map.entrySet())
        System.out.println("new key: " + entry.getKey() + " and value: " + entry.getValue());