java - Generating permutations using Hashmap

Question

I am trying to write a recursive program that can print all permutations of a list of integers taken from a file, I am using HashMap to store list, where the keys are the numbers and the values are the number of times the key occurs in the list. The code is given below:

import java.util.*;
import java.io.*;

public class perm
{
    public static void permute(HashMap<Integer, Integer> map)
    {
        if(map.isEmpty())
        {
            System.out.println();
        }
        else
        {
            Set<Integer> keys = map.keySet();
            for(int num: keys)
            {
                System.out.print(Integer.toString(num)+",");
                int val = map.get(num) -1;
                if(val == 0)
                {
                    map.remove(num);   
                }
                else
                {
                    map.put(num, val);
                }
                permute(map);
            }
        }
    }
    public static void main(String args []) throws FileNotFoundException
    {
        HashMap <Integer, Integer> map = new HashMap<Integer, Integer>();
        Scanner in = new Scanner(new File(args[0]));
        int num;
        while(in.hasNextInt())
        {
            num = in.nextInt();
            if(map.containsKey(num))
            {
                map.put(num, map.get(num)+1);
            }
            else
            {
                map.put(num,1);
            }
        }
        permute(map);
    }
}

I am getting a concurrency error, but I don't understand why, the error is given below:

Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.HashMap$HashIterator.nextNode(HashMap.java:1429)
    at java.util.HashMap$KeyIterator.next(HashMap.java:1453)
    at perm.permute(perm.java:15)
    at perm.permute(perm.java:27)
    at perm.permute(perm.java:27)
    at perm.permute(perm.java:27)
    at perm.main(perm.java:48)

--------------------Code Edited based on comments --------------------

import java.util.*;
import java.io.*;

public class perm
{
    public static void permute(HashMap<Integer, Integer> map)
    {
        if(map.isEmpty())
        {
            System.out.println();
        }
        else
        {
            Iterator it = map.entrySet().iterator(); 
            //Set<Integer> keys = map.keySet();
            while(it.hasNext())
            //for(int num: keys)
            {
                Map.Entry pair = (Map.Entry)it.next();
                int num = (int) pair.getKey();
                System.out.print(Integer.toString(num)+",");
                int val = (int) pair.getValue()-1;
                //HashMap<Integer, Integer> newMap = map;
                //int val = map.get(num) -1;
                if(val == 0)
                {
                    //newMap.remove(num);
                    it.remove(); 
                }
                else
                {
                    //newMap.put(num, val);
                    pair.setValue(val);
                }
                permute(map);
            }
        }
    }
    public static void main(String args []) throws FileNotFoundException
    {
        HashMap <Integer, Integer> map = new HashMap<Integer, Integer>();
        Scanner in = new Scanner(new File(args[0]));
        int num;
        while(in.hasNextInt())
        {
            num = in.nextInt();
            if(map.containsKey(num))
            {
                map.put(num, map.get(num)+1);
            }
            else
            {
                map.put(num,1);
            }
        }
        permute(map);
    }
}

The same error still persists. I then went back to the initial approach and stored a temporary copy of the HashMap I was trying to iterate over and modified only the temporary copy and not the original one, the same error persists.

---- Code edit based on Answer 1 ------

import java.util.*;
import java.io.*;

public class perm
{
    public static void permute(HashMap<Integer, Integer> map)
    {
        if(map.isEmpty())
        {
            System.out.println();
        }
        else
        {
            //Iterator it = map.entrySet().iterator(); 
            HashMap<Integer, Integer> newMap = map;
            Set<Integer> keys = map.keySet();
            //while(it.hasNext())
            for(int num: keys)
            {
                //Map.Entry pair = (Map.Entry)it.next();
                //int num = (int) pair.getKey();
                System.out.print(Integer.toString(num)+",");
                //int val = (int) pair.getValue()-1;
                //HashMap<Integer, Integer> newMap = map;
                int val = map.get(num) -1;
                if(val == 0)
                {
                    newMap.remove(num);
                    //it.remove(); 
                }
                else
                {
                    newMap.put(num, val);
                    //pair.setValue(val);
                }
                permute(newMap);
            }
        }
    }
    public static void main(String args []) throws FileNotFoundException
    {
        HashMap <Integer, Integer> map = new HashMap<Integer, Integer>();
        Scanner in = new Scanner(new File(args[0]));
        int num;
        while(in.hasNextInt())
        {
            num = in.nextInt();
            if(map.containsKey(num))
            {
                map.put(num, map.get(num)+1);
            }
            else
            {
                map.put(num,1);
            }
        }
        permute(map);
    }
}

I used the suggestion in the above thread but still getting the same error. — Akshay Gupta, Jun 11 '15 at 20:28
Please post your updated code. If you were using the suggestion of this thread correctly, you would not get a `ConcurrentModificationException`. — Turing85, Jun 11 '15 at 20:30
the `remove()` statement on `it` is fine. Problem is the call to `pair.setValue(...)`. You cannot add elements to a map while iterating over this map in this form. General approach is to create a new, temporary map and merge those map after the iteration. — Turing85, Jun 11 '15 at 21:01
Comment on last edit: `newMap` and `map` are the same object. The same problems apply. Can you batch your inserts/deletes and apply them after you've finished iterating? — StuPointerException, Jun 11 '15 at 21:01
I guess not since its a recursive call. I will have to go with some other direction. Thanks :) — Akshay Gupta, Jun 11 '15 at 21:20

score 2 · Answer 1 · answered Jun 11 '15 at 20:22

2

java.util.ConcurrentModificationException is thrown when you modify a collection that you are iterating over. In your case you are both iterating over and modifying the HashMap in your permute method.

If this exception was not thrown then you would end up with strange and seemingly random results each time your program ran depending on the generated hashCode of the integer being added or removed from the map.

answered Jun 11 '15 at 20:22

StuPointerException

7,117
5
29
54

To elaborate a bit more, disallowing concurrent modification enforces iteration dependability, as when you iterate over a collection you know it will not change in length or content. You can create another object that is a copy of the key List and iterate over that or keep a record of all the insertions you want to make and then make them all at once after the iteration. – csunday95 Jun 11 '15 at 20:33
In the above program I am iterating over a Set of keys, which is a separate collection from the HashMap. I am iterating over the Set and modifying the HashMap, they are two different collections, so I don't understand why it is giving this error. – Akshay Gupta Jun 11 '15 at 20:34
When you add or remove entries in a HashMap you are also modifying the keys of that HashMap (the collection you are iterating over). – StuPointerException Jun 11 '15 at 20:37

score 0 · Answer 2 · answered Jun 11 '15 at 20:32

0

you are getting ConcurrentModificationException because you are trying to modify map while iterating. Good link to understand it http://javarevisited.blogspot.com/2012/02/fail-safe-vs-fail-fast-iterator-in-java.html

answered Jun 11 '15 at 20:32

user3207081

1,451
2
11
10

java - Generating permutations using Hashmap

2 Answers2