Java ruft Details aller Teilmengen in einer Sammlung ab

In diesem Artikel wird hauptsächlich die Methode zum Abrufen aller Teilmengen in einer Menge in Java vorgestellt. Es hat einen sehr guten Referenzwert. Schauen wir es uns mit dem Herausgeber an.

Es gibt eine schriftliche Testfrage. Die allgemeine Bedeutung ist wie folgt:

Geben Sie einen Satz ein und alle Teilmengen dieser Menge ausgeben. Beispiel: Eingabe: 1, 2, 4. Das Ausgabeergebnis lautet wie folgt:

[1]
[2]
[4]
[1, 2]
[1, 4]
[2, 4]
[1, 2, 4]

Was Sie wissen müssen: Die leere Menge ist eine Teilmenge einer beliebigen Menge a Eine echte Teilmenge ist eine Teilmenge, die keine Teilmenge enthält. Eine nicht leere wahre Teilmenge enthält keine Teilmengen und keine leeren Mengen.

Lösungsideen:

Diese Frage kann sein berechnet mit der „bitweisen Korrespondenzmethode“

Zum Beispiel existiert in der Menge A={a,b,c} für jedes Element in jeder Teilmenge entweder das Element oder es existiert nicht. Zuordnung zu einer Teilmenge:

(a,b,c)
(1,1,1)->(a,b,c)
(1,1,0)->(a,b)
(1,0,1)->(a,c)
(1,0,0)->(a)
(0,1,1)->(b,c)
(0,1,0)->(b)
(0,0,1)->(c)
(0,0,0)->@(@表示空集)

Beachten Sie die oben genannten Regeln, die der Datenspeichermethode in Computern ähneln, damit Sie eine Ganzzahl einer Menge zuordnen können...000 ~ 111...111 ( Das heißt, es gibt, bedeutet keine und umgekehrt. Durch schrittweises Erhöhen der Ganzzahl können alle Zahlen durchlaufen werden, dh die entsprechende Teilmenge der Menge kann erhalten werden.

Der Haupttest ist die Verschiebungsoperation und die Fähigkeit zum logischen Denken. Der spezifische Code lautet wie folgt (von dieser Maschine authentifiziert und absolut zuverlässig):

import java.util.ArrayList;
import java.util.Scanner;
import org.apache.commons.collections.CollectionUtils;
/**
 * 输入一个集合，输出这个集合的所有子集
 * @author liangyongxing
 * @time 2017-02-06
 */
public class SubListExport {
 public static void main(String[] args) {
  ArrayList<Integer> list = new ArrayList<Integer>();
  System.out.println("请输入一串整数并在输入时用英文逗号隔开：");
  String inputString = new Scanner(System.in).next().toString();
  if (inputString != null && !inputString.isEmpty()) {
   String[] strArray = inputString.split(",");
   for (String str : strArray) {
    list.add(Integer.parseInt(str));
   }
   ArrayList<ArrayList<Integer>> allsubsets = getSubsets(list); 
   for(ArrayList<Integer> subList : allsubsets) {
    System.out.println(subList);
   }
  }
 }
 public static ArrayList<ArrayList<Integer>> getSubsets(ArrayList<Integer> subList) {
  ArrayList<ArrayList<Integer>> allsubsets = new ArrayList<ArrayList<Integer>>();
  int max = 1 << subList.size();
  for(int loop = 0; loop < max; loop++) {
   int index = 0;
   int temp = loop;
   ArrayList<Integer> currentCharList = new ArrayList<Integer>();
   while(temp > 0) {
    if((temp & 1) > 0) {
     currentCharList.add(subList.get(index));
    }
    temp>>=1;
    index++;
   }42    allsubsets.add(currentCharList);44   }
  return allsubsets;
 }
}

Hinweis: 2017-02-08 10:01:32 Der obige Code weist bestimmte Lücken auf, das heißt, wenn die Eingabe wiederholte Zahlen enthält, werden im Ergebnis wiederholte Teilmengen ausgegeben, was die Anforderungen der Frage nicht erfüllt und muss berechnet werden, wenn die Teilmengen berechnet werden. Das endgültige Druckergebnis kann aus den Sätzen erhalten werden. Die spezifischen Änderungsdetails sind in der folgenden Abbildung dargestellt:

1. Ändern Sie den akzeptierten Rückgabewert dort, wo die Hauptfunktion ausgibt: HashSet-Typ

2. Sie müssen die Kapselungsliste ändern und die Liste so ändern, dass sie festgelegt wird

Die Änderung ist nun abgeschlossen und die Ergebnisse des Testlaufs lauten wie folgt:

Eine Analyse des Codes ist möglich. Seine zeitliche Komplexität beträgt: O(n*log2n)

Das obige ist der detaillierte Inhalt vonJava ruft Details aller Teilmengen in einer Sammlung ab. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!