Heim  >  Artikel  >  Java  >  Teilen von Java-Beispielcode zum Lösen von Teilmengen

Teilen von Java-Beispielcode zum Lösen von Teilmengen

黄舟
黄舟Original
2017-10-16 10:07:481542Durchsuche

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(&#39;b&#39;,&#39;c&#39;,&#39;d&#39;)); 
  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!

Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn