java求解集合的子集的实例_Java教程

java求解集合的子集的实例

2021-01-18 10:15尚云峰111 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; 

									}