java求解集合的子集的实例

 java求解集合的子集的实例

方式1:我们知道子集个数 2的n次方

比如a,b,c的子集

     * 000  0  {}
     *001  1   a
     *010  2   b
     *011  3   a,b (b,a)
     *100  4   c
     * 101  5   a,c (c,a)
     * 110  6   b,c (c,b)
     * 111  7   a,b,c

利用二进制的对应关系

@test 
public void test1() throws exception { 
   
  set<arraylist<integer>> subsets = getsubsets( arrays.aslist(1,2,6)); 
  set<arraylist<string>> subsets2 = getsubsets( arrays.aslist("a","b","c")); 
  set<arraylist<character>> subsets3 = getsubsets( arrays.aslist('b','c','d')); 
  system.out.println(subsets); 
  system.out.println(subsets2); 
  system.out.println(subsets3); 
} 
 
//集合接受各种类型数据 
public <t> set<arraylist<t>> getsubsets(list<t> sublist) { 
  //考虑去重 
  set<arraylist<t>> allsubsets = new linkedhashset<>(); 
  int max = 1 << sublist.size(); 
  for (int loop = 0; loop < max; loop++) { 
    int index = 0; 
    int temp = loop; 
    arraylist <t> currentcharlist = new arraylist<t>(); 
    //控制索引 
    while (temp > 0) { 
      if ((temp & 1) > 0) { 
        currentcharlist.add(sublist.get(index)); 
      } 
      temp >>= 1; 
      index++; 
    } 
    allsubsets.add(currentcharlist); 
  } 
  return allsubsets; 
} 

方式2:归纳法

   @test 
public void testname() throws exception { 
  set<list<integer>> subsets2 = getsubsets2(arrays.aslist(1,2,3)); 
  system.out.println(subsets2); 
} 
 
//方式2 归纳法 
//从{}和最后一个元素开始,每次迭代加一个元素组成一个新的集合 
public  set<list<integer>> getsubsets2(list<integer> list) { 
   if (list.isempty()) { 
     set<list<integer>> ans=new linkedhashset<>(); 
     ans.add(collections.emptylist()); 
     return ans; 
   } 
    
   integer first=list.get(0); 
   list<integer> rest=list.sublist(1, list.size()); 
   set<list<integer>> list1 = getsubsets2(rest); 
   set<list<integer>> list2 = insertall(first, list1);// 
   system.out.println(list1); 
   system.out.println(list2); 
   system.out.println("================"); 
   return concat(list1, list2); 
} 
 
 
   public  set<list<integer>> insertall(integer first,set<list<integer>> lists){ 
  // 
  set<list<integer>> result=new linkedhashset<>(); 
  for (list<integer> list : lists) { 
    list<integer> copy=new arraylist<>(); 
    copy.add(first); 
    copy.addall(list); 
    result.add(copy); 
  } 
  return result; 
} 
   
  //这样写可以不影响lists1,lists2的值 
  private set<list<integer>> concat(set<list<integer>> lists1,set<list<integer>> lists2) { 
  set<list<integer>> temp=new linkedhashset<>(lists1); 
  temp.addall(lists2); 
  return temp; 
} 

如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！