Java get details of all subsets in a collection-javaTutorial-php.cn

Java get details of all subsets in a collection

黄舟

Release： 2017-03-09 10:11:21

Original

2945 people have browsed it

This article mainly introduces Java's method of obtaining all subsets in a collection. It has a very good reference value. Let’s take a look at it with the editor.

There is a written test question in the interview. The general meaning is as follows:

Input a set and output all subsets of this set. . For example, input: 1, 2, 4. The output result is as follows:

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

Copy after login

What you need to know: The empty set is a subset of any set; a proper subset is a set that does not contain a subset; A non-empty proper subset means that it does not contain subsets and empty sets

Solution ideas:

This question can be calculated using the "bitwise correspondence method"

For example, set A={a,b,c}, for any element, it either exists or does not exist in each subset. Mapping to a subset:

(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)->@(@表示空集)

Copy after login

Observe the above rules, which are similar to the data storage method in computers, so you can map an integer to a set...000 ~ 111...111 (meaning yes, meaning no , and vice versa), by gradually increasing the integer number, all the numbers can be traversed, that is, the corresponding subset of the set can be obtained.

The main test is displacement operation and logical thinking ability. The specific code is as follows (authenticated by this machine and absolutely reliable):

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

Copy after login

Note: 2017-02-08 10:01:32 The above code has certain loopholes, that is, when the input has repeated numbers, the result will have repeated subsets output, which does not meet the requirements of the question. It is necessary to add HashSet when calculating the subsets. Perform duplication elimination, and the final printing result can be obtained from sets. The specific modification details are as shown in the figure below:

#1. Modify the accepted return value to the HashSet type where the main function prints

2. In the function part, you need to modify the encapsulation list and change the list to set

The modification is now complete, and the test running results are as follows:

Analyzing the code can determine it The time complexity is: O(n*log2n)

The above is the detailed content of Java get details of all subsets in a collection. For more information, please follow other related articles on the PHP Chinese website!