属性值的组合

Question

我努力生成属性列表的所有可能的值组合。例如，对于三个属性 A、B、C，具有以下值：{a1,a2} 为 A，{b1,b2} 为 B，{c1,c2} 为 C，我应该得到 8 种组合：

a1,b1,c1

a1,b1,c2

a1,b2,c1

a1,b2,c2

a2,b1,c1

a2,b1,c2

a2,b2,c1

a2,b2,c2

我使用了以下两个递归 java 函数，其中attribute_to_domainis aMap我们将每个属性作为 akey并将其值作为 a value，并将每个组合作为 an 添加<ArrayList<String>到enumerate_tuples作为 anArrayList<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);

        }

}

我遇到的问题是enumerate_tuples空元素，我无法通过调用保留发生在它上面的更改。

请问我该如何解决这个问题？提前致谢。

Answer 1

有一种更简单、更快的解决方案，不需要递归。可以提前计算输出组合的数量：在您的情况下乘以属性，2*2*2但对于每个组合都是如此。此外，我们可以根据组合索引计算每个组合中将放置哪个值。如果我们假设组合索引从0至7：用于A：-组合0-3将包含a1-组合4-7将包含a2对B-组合0,1,4,5将包含b1-组合2,3,6,7-将包含b2for&nbsp;C- 组合 0,2,4,6 将包含c1- 组合 1,3,5,7 将包含c2因此，值放置的公式基于组合索引、属性的顺序（A第一个等）以及属性中值的顺序。该算法的复杂度为 o(n*m)，其中 n 是属性数和 m 值数。

Answer 2

从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 {&nbsp; &nbsp; public static Set<Set<Object> > cartesianProduct(Set<?>... sets) {&nbsp; &nbsp; &nbsp; &nbsp; if (sets.length < 2)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; throw new IllegalArgumentException(&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; "Can't have a product of fewer than two sets (got " +&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sets.length + ")");&nbsp; &nbsp; &nbsp; &nbsp; return _cartesianProduct(0, sets);&nbsp; &nbsp; }&nbsp; &nbsp; private static Set<Set<Object> > _cartesianProduct(int index, Set<?>... sets) {&nbsp; &nbsp; &nbsp; &nbsp; Set<Set<Object> > ret = new TreeSet<Set<Object> >(new Comparator<Set<Object> >() {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; @Override&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; public int compare(Set<Object> o1, Set<Object> o2) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return o1.toString().compareTo(o2.toString());&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; });&nbsp; &nbsp; &nbsp; &nbsp; if (index == sets.length) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ret.add(new TreeSet<Object>());&nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (Object obj : sets[index]) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for (Set<Object> set : _cartesianProduct(index+1, sets)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; set.add(obj);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ret.add(set);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return ret;&nbsp; &nbsp; }&nbsp; &nbsp; public static void main(String[] args) {&nbsp; &nbsp; &nbsp; &nbsp; Map<String, Set<String> > dataMap = new HashMap<String, Set<String> >();&nbsp; &nbsp; &nbsp; &nbsp; dataMap.put("A", new TreeSet<String>(Arrays.asList("a1", "a2")));&nbsp; &nbsp; &nbsp; &nbsp; dataMap.put("B", new TreeSet<String>(Arrays.asList("b1", "b2")));&nbsp; &nbsp; &nbsp; &nbsp; dataMap.put("C", new TreeSet<String>(Arrays.asList("c1", "c2")));&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(cartesianProduct(dataMap.values().toArray(new Set<?>[0])));&nbsp; &nbsp; }}