属性值的组合

Question

我努力生成属性列表的所有可能的值组合。例如，对于三个属性 A、B、C，具有以下值：{a1,a2} 为 A，{b1,b2} 为 B，{c1,c2} 为 C，我应该得到 8 种组合：a1,b1,c1a1,b1,c2a1,b2,c1a1,b2,c2a2,b1,c1a2,b1,c2a2,b2,c1a2,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-将包含b2
for 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 {

    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])));

    }

}