1

我需要一个用java编写的算法来计算以下内容：

给定一个集合 S = {s1,s2,...,sn}，其中 n 个元素表示类型和集合 s1_alternatives ={s1a,s1b,...,s1z} , s2_alternatives ={s2a,s2b,...,s2z} ,..., sn_alternatives = {sna,snb,...,snz},

通过将集合 S 的元素替换为集合 s1_alternatives、s2_alternatives、...、sn_alternatives 的替代元素来计算集合 S 集合的所有可能组合。

示例：给定 S = {a,b,c} 和一组备选方案 a_alternatives = {a1,a2,a3}，b_alternatives = {b1,b2}，c_alternatives = {c1,c2}。S 的元素及其替代项的一些可能组合是 S_ALTERNATIVES = {{a1,b1,c1},{a2,b1,c1},{a3,b1,c2},...}。

我正在寻找一种用 java 编写的解决方案，该解决方案可以应用于任意大小的任何集合（任何对象类型且不限于字符串）。

我已经尝试过这段代码，但我需要适当的停止条件才能在适当的地方进行递归。12 套组合我只得到 5 套！：

组合：必须从中构建所有组合的集合

type2Words：所有替换选项

getType：给出给定元素的类型

结果：所有组合的可能集合

void calculateAllCombinations(Set<String> combination,
Map<String, Set<String>> type2Words, Map<String,String> getType,
Set<Set<String>>result)
{   
  Set<String> wordOfStartCombination = new HashSet<String>(combination);

  for(String wordPlaceHolder:wordOfStartCombination)
  {
     String type = getType.get(wordPlaceHolder);
     Set<String> allWithThisType = type2Words.get(type);

     for(String thisType:allWithThisType)
     {
        Set<String> wordTemp = new HashSet<String>(combination);
        wordTemp.remove(wordPlaceHolder);
        wordTemp.add(thisType);
        result.add(wordTemp);
        if(!result.contains(wordTemp))
           calculateAllCombinations(wordTemp,type2Words,getType,result);
     }          
   }
 }

public static void main(String args[])
{
    Set<String> startCombination = new HashSet<String>();
    startCombination.add("a1");startCombination.add("b1"); startCombination.add("c1");


    Map<String,String> getType = new HashMap<String, String>();
    getType.put("a1", "type_a");
    getType.put("a2", "type_a");
    getType.put("a3", "type_a");
    getType.put("b1", "type_b");
    getType.put("b2", "type_b");
    getType.put("c1", "type_c");
    getType.put("c2", "type_c");
    Map<String,Set<String>> type2Word = new HashMap<String, Set<String>>();

    Set<String> typedSet1 = new HashSet<String>();
    typedSet1.add("a1");typedSet1.add("a2");typedSet1.add("a3");type2Word.put("type_a", typedSet1);

    Set<String> typedSet2 = new HashSet<String>();
    typedSet2.add("b1");typedSet2.add("b2");type2Word.put("type_b", typedSet2);

    Set<String> typedSet3 = new HashSet<String>();
    typedSet3.add("c1");typedSet3.add("c2");type2Word.put("type_c", typedSet3);

    Set<Set<String>> result = new HashSet<Set<String>>();
    result.add(startCombination);   

    calculateAllCombinations(startCombination,type2Word,getType,result);
    for(Set<String> word:result)
        System.out.println(word);
}
4

0 回答 0