Iterating over sets of numbers

Question

I have 3 different sets of numbers, for example
a={1,3,4}
b={2,6}
c={0}

the size of sets can be variable, e.g. one set with 5 elements, another with 3, etc.

I have saved these values in a hashmap in java,

HashMap H=new HashMap<String,HashSet<Integer>>();

for this example, the keys of H are "a","b",and "c".

I want to make all possible combinations of the numbers in these three sets, that is:
1,2,0
1,6,0
3,2,0
3,6,0
4,2,0
4,6,0

But I have a problem. The number of sets can also be variable, i.e. my HashMap can have 3 to 10 keys. Do you have any idea how I should iterate over the hashmap, so that I can make all possible combinations?

ANSWER: I changed the HashMap to Vector, however, it also works with HashMap with little changes

call the function as follow:

Iterate_over_map(0,new Integer[h.size()],h,final_list);


Iterate_over_map(int count,Integer[] curr,Vector<HashSet<Integer>> h,Vector<Integer[]> final_list)
{
    if(count>=h.size())
    {
        final_list.addElement(curr.clone());
        return;
    }

    int next_count=count+1;
    for (Integer element:h.elementAt(count))
    {

        curr[count]=element;
        Iterate_over_map(next_count,curr,h,final_list);
    }

}

OLD solution

for(int x:H.get("a"))
{
    v[0]=x;//node1 (an ortholog of node1)
    for(int y:H.get("b"))
    {
        v[1]=y;//node2 (an ortholog of node2)
        for(int z:H.get("c"))
        {
            v[2]=z;//node3 (an ortholog of node3)
        }
    }
}

thanks a lot.

no, it is not homework. it is a very small part of my project. — Pegah, May 01 '13 at 10:50
you can use an iterator on the hashmap; cf example http://stackoverflow.com/questions/1066589/java-iterate-through-hashmap — Kidi, May 01 '13 at 10:51
thanks for your answer. I know how to iterate over hashmap. I don't know how to make the output that I have mentioned. first I wrote 3 for loop, each was iterating over one of the keys. But when then number of nodes is more than 3, I should always increase the number of for s! — Pegah, May 01 '13 at 10:53

score 2 · Answer 1 · answered May 01 '13 at 11:55

You should use recursive function. I do example

public static void main(String[] args) {
    String[] keys = map.keySet().toArray(new String[0]);
    loopMap(map, keys, 0, "");
}

public static void loopMap(Map<String, Set<Integer>> map, String[] keys, int index, String res) {
    if (index == keys.length) {
        System.out.println(res);
        return;
    }
    Set<Integer> set = map.get(keys[index]);

    for(Integer ele : set) {
        loopMap(map, keys, index + 1, res + ele);
    }
}

With: map use LinkedHashMap, set is LinkedHashSet and check null ^^

Hey! thanks a lot. I did not thought about recursive. thanks again. — Pegah, May 01 '13 at 15:01

score 2 · Accepted Answer · answered May 01 '13 at 12:10

You need to use recursion instead of your nested loops, this will do what you want:

public static void main(String[] args) 
{
  List<List<Integer>> integers = new ArrayList<List<Integer>>();
  integers.add(Arrays.asList(1, 3, 4));
  integers.add(Arrays.asList(2, 6));
  integers.add(Arrays.asList(0));

  List<List<Integer>> combinations = combine(integers);

  System.out.println(combinations);
}

private static List<List<Integer>> combine(List<List<Integer>> allIntegers) 
{
  List<Integer> integers = allIntegers.remove(0);
  List<List<Integer>> allCombinations = new ArrayList<List<Integer>>();

  for (Integer i : integers) 
  {
    if (allIntegers.isEmpty()) 
    {
      allCombinations.add(new ArrayList<Integer>(Arrays.asList(i)));
    }
    else 
    {
      for (List<Integer> combinations : combine(new ArrayList<List<Integer>>(allIntegers))) 
      {
        combinations.add(0, i);
        allCombinations.add(combinations);
      }
    }
  }

  return allCombinations;
}

Which produces the output:

[[1, 2, 0], [1, 6, 0], [3, 2, 0], [3, 6, 0], [4, 2, 0], [4, 6, 0]]

Iterating over sets of numbers

2 Answers2