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);
}
//集合接受各种类型数据
publicSet>getSubsets(ListsubList){
//考虑去重
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(Listlist){
if(list.isEmpty()){
Set>ans=newLinkedHashSet<>();
ans.add(Collections.emptyList());
returnans;
}
Integerfirst=list.get(0);
Listrest=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(Listlist:lists){
Listcopy=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（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。