时间戳

首页 > 解决方案 > 属性值的组合

java - 属性值的组合

问题描述

我很难生成属性列表的所有可能的值组合。例如，对于具有以下值的三个属性 A、B、C：A 的 {a1,a2}、B 的 {b1,b2} 和 C 的 {c1,c2}，我应该得到 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 函数 where attribute_to_domainis aMap我们将每个属性作为 akey并将其值作为 a value，我们将每个组合作为 an添加<ArrayList<String>为enumerate_tuplesArrayList<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空元素，我无法保留通过调用对其进行的更改。

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

标签： javarecursionarraylisthashmap

解决方案

有一种更简单、更快的解决方案，不需要递归。

可以提前计算输出组合的数量：在您的情况下，属性相乘，2*2*2但对于每个组合都是如此。

此外，我们可以根据组合索引计算出每个组合中将放置哪个值。如果我们假设组合索引从 0 到 7：
for A:
- 组合 0-3 将包含a1
- 组合 4-7 将包含a2
for 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 值数。

推荐阅读