Detaillierte Erläuterung der Java-Implementierungsmethode zum Finden aller Teilmengen einer Menge durch Bitoperationen

Der Editor unten stellt Ihnen eine Java-Methode vor, mit der Sie alle Teilmengen einer Menge durch Bitoperationen finden können. Der Herausgeber findet es ziemlich gut, deshalb werde ich es jetzt mit Ihnen teilen und es allen als Referenz geben. Folgen wir dem Editor und werfen wir einen Blick darauf

Java verfügt nicht über eine eigene Methode, um alle Teilmengen einer Menge zu finden. Wir können sie über die Teilmengenregeln der Menge finden.

Alle Teilmengen einer Menge sind gleich 2^der Länge der Menge. Beispielsweise beträgt die Länge von {c,b,a} 3 und es gibt 8 Teilmengen dieser Menge.

Dieser Satz scheint einfach, enthält aber auch tiefgreifende Philosophie. Tatsächlich beziehen sich alle Mengen einer Menge auf die Zahl 2^die Länge der Menge. Im obigen Beispiel beträgt die Länge von {c, b, a} beispielsweise 3, dann können 0-7 verwendet werden, um alle Teilmengen darzustellen. Wie unten gezeigt, bedeutet das Ändern der Position, die der Zahl entspricht, auf 1, dass ich diese Zahl benötige, um eine Teilmenge zu bilden. Die binäre Darstellung von 0 bis 7 repräsentiert lediglich alle Teilmengen mit einer Länge von 3 und einer Anzahl von 8 Teilmengen.

0(000): {}

1(001): {a}

2(010): {b}

3(011 )? }

7(111): {a,b,c}

Nach den oben genannten Regeln kann der Code also so geschrieben werden: Nehmen Sie zuerst die Länge der Menge und Finden Sie heraus, 2^Die Länge des Satzes ist Wie viele, wie oben 8, und durchlaufen Sie dann von 0 bis 8-1. Führen Sie beim Durchlaufen Bitoperationen für alle Daten 0, 1, 2 ... durch und bestimmen Sie nacheinander die entsprechende Anzahl von Ziffern, dh in binärer Darstellung, welche Ziffer 1 ist. Verwenden Sie Assembly, verschieben Sie jedes Bit an das Ende und implementieren Sie das Bit mit 1. Der spezifische Code lautet wie folgt:

Die Laufergebnisse lauten wie folgt:

import java.util.ArrayList;
public class getSubSet {
 public static ArrayList<ArrayList<Integer>> getSubset(ArrayList<Integer> L) {
		if (L.size() > 0) {
			ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
			for (int i = 0; i < Math.pow(2, L.size()); i++) {// 集合子集个数=2的该集合长度的乘方
				ArrayList<Integer> subSet = new ArrayList<Integer>();
				int index = i;// 索引从0一直到2的集合长度的乘方-1
				for (int j = 0; j < L.size(); j++) {
					// 通过逐一位移，判断索引那一位是1，如果是，再添加此项
					if ((index & 1) == 1) {// 位与运算，判断最后一位是否为1
						subSet.add(L.get(j));
					}
					index >>= 1;// 索引右移一位
				}
				result.add(subSet); // 把子集存储起来
			}
			return result;
		} else {
			return null;
	}
}

	public static void main(String[] args) {
	ArrayList<Integer> L = new ArrayList<Integer>();
	L.add(1);
	L.add(2);
	L.add(3);
	System.out.println(getSubset(L));
	}

}

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung der Java-Implementierungsmethode zum Finden aller Teilmengen einer Menge durch Bitoperationen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!