Combinations of attributes values

Question

I struggle with generating all possible combinations of values of a List of Attributes. As an example, for three attributes A, B,C, with the following values:{a1,a2} for A ,{b1,b2} for B, and {c1,c2} for C, I should get 8 combinations:

a1,b1,c1
a1,b1,c2
a1,b2,c1
a1,b2,c2
a2,b1,c1
a2,b1,c2
a2,b2,c1
a2,b2,c2

I used the following two recursive java functions where attribute_to_domain is a Map where we put each attribute as a key and its values as a value, and we add each combination as an <ArrayList<String> toenumerate_tuples as an ArrayList<ArrayList<String>>

    public  void fillTuples(Map<String, Set<String>> attribute_to_domain, ArrayList<String> attributes, ArrayList<ArrayList<String>> enumerate_tuples)
{      
        for (Map.Entry<String, Set<String>> entrySet :attribute_to_domain.entrySet()) {
         String attribute=entrySet.getKey();
         attributes.add(attribute);
        }
    int pos = 0;
    Set<String> domain = attribute_to_domain.get(attributes.get(pos));
        for (Iterator<String> it = domain.iterator(); it.hasNext();) {
               String val = it.next();
            ArrayList<String> tuple=new ArrayList<String>();
            tuple.add(val);
                fillTuples(attribute_to_domain, attributes, 1, tuple, enumerate_tuples);
          tuple.remove(tuple.size()-1);
          assert(tuple.isEmpty());
          }

      }
public  void fillTuples(Map<String, Set<String>> attribute_to_domain, ArrayList<String> attributes, int pos, ArrayList<String> tuple,  ArrayList<ArrayList<String>>  enumerate_tuples)
{                              
    assert(tuple.size() == pos);
    if (pos == attributes.size())
    {      
       enumerate_tuples.add(tuple);
       return;
    }

        Set<String> domain = attribute_to_domain.get(attributes.get(pos));
        for (Iterator<String> it = domain.iterator(); it.hasNext();) {
          String val = it.next();
          tuple.add(val);
          fillTuples(attribute_to_domain, attributes, pos+1, tuple, enumerate_tuples);
          tuple.remove(tuple.size()-1);
        }

}

The problem that I get enumerate_tuples with empty elements and I can not keep changes that happened on it through the calls.

How can I solve this problem, please? Thanks in advance.

and why the wierd method name? where's that convention coming from? — Sharon Ben Asher, Oct 15 '18 at 06:56
Please read about java naming conventions. You are violating them all over the place, and that makes your code really hard to read for people used to read java code. And: read about the pros (and many cons) of using assert() in Java. Most of the time, it is really a bad idea. Then I am wondering why use *Iterators* to iterate simple sets. Your code is rally the opposite of idiomatic Java ... — GhostCat, Oct 15 '18 at 07:13
Actually, I converted the code from C++ to Java, so I think the problem arises from passing parameters by references in C++ and by values in Java. — eng.Hiba, Oct 15 '18 at 07:28

Sharon Ben Asher · Answer 1 · 2018-10-15T07:37:13.310

There is a simpler and faster solution, one that does not require recursion.

The number of output combinations can be calculated in advanced: multiplication of attributes in your case 2*2*2 but it is true for every combination.

Furthermore, we can calculate which value will be placed in each combination based on the combination index. if we assume combination index goes from 0 to 7:
for A:
- combinations 0-3 will contain a1
- combinations 4-7 will contain a2
for B
- combinations 0,1,4,5 will contain b1
- combinations 2,3,6,7 will contain b2
for C
- combinations 0,2,4,6 will contain c1
- combinations 1,3,5,7 will contain c2

so the formula for value placement is based on the combination index, the order of the attributes (A first etc) and the order of the values in the attribute.

the complexity of this algorithm is o(n*m) where n is number of attributes and m number of values.

Thanks for your answer, but I need a general solution for coding. — eng.Hiba, Oct 16 '18 at 02:16
This is "a general solution for coding". do you mean you need someone to code it for you? — Sharon Ben Asher, Oct 16 '18 at 06:53

Miller Cy Chan · Accepted Answer · 2018-10-18T02:34:21.360

Revised from Cartesian product of arbitrary sets in Java

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;

import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

public class CartesianProduct {

    public static Set<Set<Object> > cartesianProduct(Set<?>... sets) {
        if (sets.length < 2)
            throw new IllegalArgumentException(
                    "Can't have a product of fewer than two sets (got " +
                    sets.length + ")");

        return _cartesianProduct(0, sets);
    }

    private static Set<Set<Object> > _cartesianProduct(int index, Set<?>... sets) {
        Set<Set<Object> > ret = new TreeSet<Set<Object> >(new Comparator<Set<Object> >() {
            @Override
            public int compare(Set<Object> o1, Set<Object> o2) {
                return o1.toString().compareTo(o2.toString());
            }
        });

        if (index == sets.length) {
            ret.add(new TreeSet<Object>());
        } else {
            for (Object obj : sets[index]) {
                for (Set<Object> set : _cartesianProduct(index+1, sets)) {
                    set.add(obj);
                    ret.add(set);
                }
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        Map<String, Set<String> > dataMap = new HashMap<String, Set<String> >();
        dataMap.put("A", new TreeSet<String>(Arrays.asList("a1", "a2")));
        dataMap.put("B", new TreeSet<String>(Arrays.asList("b1", "b2")));
        dataMap.put("C", new TreeSet<String>(Arrays.asList("c1", "c2")));

        System.out.println(cartesianProduct(dataMap.values().toArray(new Set<?>[0])));
    }

}

Thanks for your answer. I have tried it, but I got errors on long return statement where many symbol can not be found like e1,e2 stream, toList, and orElse. It will be so appreciated if you can correct my code. Thanks again. — eng.Hiba, Oct 16 '18 at 02:25
Thanks a lot. Could you please recommend me how can we pass sets from a predefined "dataMap" to "cartesianProduct" with unknown size. — eng.Hiba, Oct 17 '18 at 05:49
Please see the updated the answer: cartesianProduct(dataMap.values().toArray(new Set>[0])) — Miller Cy Chan, Oct 18 '18 at 02:38

Combinations of attributes values

2 Answers2