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 publicvoidtest1()throwsException{ Set>subsets=getSubsets(Arrays.asList(1,2,6)); Set >subsets2=getSubsets(Arrays.asList("a","b","c")); Set >subsets3=getSubsets(Arrays.asList('b','c','d')); System.out.println(subsets); System.out.println(subsets2); System.out.println(subsets3); } //集合接受各种类型数据 public Set >getSubsets(List subList){ //考虑去重 Set >allsubsets=newLinkedHashSet<>(); intmax=1< currentCharList=newArrayList (); //控制索引 while(temp>0){ if((temp&1)>0){ currentCharList.add(subList.get(index)); } temp>>=1; index++; } allsubsets.add(currentCharList); } returnallsubsets; }
方式2:归纳法
@Test publicvoidtestName()throwsException{ Set>subsets2=getSubsets2(Arrays.asList(1,2,3)); System.out.println(subsets2); } //方式2归纳法 //从{}和最后一个元素开始,每次迭代加一个元素组成一个新的集合 publicSet
>getSubsets2(List
list){ if(list.isEmpty()){ Set >ans=newLinkedHashSet<>(); ans.add(Collections.emptyList()); returnans; } Integerfirst=list.get(0); List
rest=list.subList(1,list.size()); Set >list1=getSubsets2(rest); Set
>list2=insertAll(first,list1);// System.out.println(list1); System.out.println(list2); System.out.println("================"); returnconcat(list1,list2); } publicSet
>insertAll(Integerfirst,Set
>lists){ // Set
>result=newLinkedHashSet<>(); for(List
list:lists){ List copy=newArrayList<>(); copy.add(first); copy.addAll(list); result.add(copy); } returnresult; } //这样写可以不影响lists1,lists2的值 privateSet >concat(Set
>lists1,Set
>lists2){ Set
>temp=newLinkedHashSet<>(lists1); temp.addAll(lists2); returntemp; }
如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:czq8825#qq.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。