Explication détaillée de la méthode d'implémentation de Java pour trouver tous les sous-ensembles d'un ensemble via des opérations sur les bits

L'éditeur ci-dessous vous proposera une méthode Java pour trouver tous les sous-ensembles d'un ensemble via des opérations sur les bits. L'éditeur le trouve plutôt bon, je vais donc le partager avec vous maintenant et le donner comme référence pour tout le monde. Suivons l'éditeur et jetons un œil

Java n'a pas sa propre méthode pour trouver tous les sous-ensembles d'un ensemble. Nous pouvons le trouver grâce aux règles de sous-ensemble de l'ensemble.

Tous les sous-ensembles d'un ensemble sont égaux à 2^la longueur de l'ensemble. Par exemple, la longueur de {c,b,a} est 3 et il existe 8 sous-ensembles de cet ensemble.

Cette phrase semble simple, mais elle contient aussi une philosophie profonde. En fait, tous les ensembles d'un ensemble sont liés au nombre 2^la longueur de l'ensemble. Par exemple, dans l'exemple ci-dessus, la longueur de {c, b, a} est 3, alors 0-7 peut être utilisé pour représenter tous ses sous-ensembles. Comme indiqué ci-dessous, changer la position correspondant au nombre en 1 signifie que j'ai besoin de ce nombre pour former un sous-ensemble. La représentation binaire de 0 à 7 représente simplement tous les sous-ensembles d'une longueur de 3 et d'un nombre de 8 sous-ensembles.

0(000) : {}

1(001) : {a}

2(010) : {b}

3(011 ) : {ab}

4(100) : {c}

5(101) : {a,c>

6(110) : {b,c >

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

Donc, selon les règles ci-dessus, le code peut être écrit comme ceci, prenez d'abord la longueur de l'ensemble, et découvrez 2 ^ La longueur de l'ensemble est de combien, comme 8 ci-dessus, puis passez de 0 à 8-1. Lors du parcours, effectuez des opérations binaires sur chaque donnée 0, 1, 2... et déterminez le nombre de chiffres correspondant un par un, c'est-à-dire en représentation binaire, quel chiffre est 1. Utilisez l'assembly, déplacez chaque bit jusqu'à la fin et implémentez le bit avec 1. Le code spécifique est le suivant :

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));
	}

}

Les résultats en cours d'exécution sont les suivants :

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!