欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

java求解集合的子集的实例

程序员文章站 2024-04-01 20:57:34
 java求解集合的子集的实例 方式1:我们知道子集个数 2的n次方 比如a,b,c的子集      * 0...

 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; 
} 



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