In diesem Artikel werden hauptsächlich relevante Informationen zum Lösen von Teilmengen in Java vorgestellt. Ich hoffe, dass dieser Artikel jedem helfen kann, diese Methode zu beherrschen
Java Beispiel für die Lösung einer Teilmenge einer Menge
Methode 1: Wir kennen die n-te Potenz der Anzahl der Teilmengen 2
Zum Beispiel die Teilmengen von 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
im Binärformat Korrespondenz
@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; }
Methode 2: Induktionsmethode
@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; }
Das obige ist der detaillierte Inhalt vonTeilen von Java-Beispielcode zum Lösen von Teilmengen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!