java求解集合的子集的实例

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> 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 = new LinkedHashSet<>();

int max = 1 << subList.size();

for (int loop = 0; loop < max; loop++) {

int index = 0;

int temp = loop;

ArrayList currentCharList = new ArrayList();

//控制索引

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> subsets2 = getSubsets2(Arrays.asList(1,2,3));

System.out.println(subsets2);

}

//方式2 归纳法

//从{}和最后一个元素开始,每次迭代加一个元素组成一个新的集合

public Set> getSubsets2(List list) {

if (list.isEmpty()) {

Set> ans=new LinkedHashSet<>();

ans.add(Collections.emptyList());

return ans;

}

Integer first=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("================");

return concat(list1, list2);

}

public Set> insertAll(Integer first,Set> lists){

//

Set> result=new LinkedHashSet<>();

for (List list : lists) {

List copy=new ArrayList<>();

copy.add(first);

copy.addAll(list);

result.add(copy);

}

return result;

}

//这样写可以不影响lists1,lists2的值

private Set> concat(Set> lists1,Set> lists2) {

Set> temp=new LinkedHashSet<>(lists1);

temp.addAll(lists2);

return temp;

}

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。