Detailed explanation of Java's implementation method of finding all subsets of a set through bit operations

The following editor will bring you a Java method to find all subsets of a set through bit operations. The editor thinks it is quite good, so I will share it with you now and give it as a reference for everyone. Let’s follow the editor and take a look.

Java does not have a built-in method to find all subsets of a set. We can find it through the subset rules of the set.

All subsets of a set are equal to 2^the length of the set. For example, the length of {c,b,a} is 3, and there are 8 subsets of this set.

This sentence seems very simple, but it also contains profound philosophy. In fact, all sets of a set are related to the number 2^the length of the set. For example, in the above example, if the length of {c, b, a} is 3, then 0-7 can be used to represent all its subsets. As shown below, changing the position corresponding to the number to 1 means that I need this number to form a subset. The binary representation from 0 to 7 just represents all subsets with a length of 3 and a number of 8 subsets.

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}

So, according to the above rules, the code can be written like this, first take the length of the set, and find out 2^The length of the set is How many, such as 8 above, and then traverse from 0 to 8-1. When traversing, perform bit operations on each data 0, 1, 2... and determine the corresponding number of digits one by one, that is, in binary representation, which digit is 1. Use assembly, move each bit to the end, and implement it with the bit of 1. The specific code is as follows:

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

}

Run The results are as follows:

The above is the detailed content of Detailed explanation of Java's implementation method of finding all subsets of a set through bit operations. For more information, please follow other related articles on the PHP Chinese website!