자바 집합 에 있 는 모든 부분 집합 얻 기

면접 중 에 필기시험 문제 가 하나 있 는데,대략적인 뜻 은 다음 과 같다.
집합 을 입력 하여 이 집합의 모든 부분 집합 을 출력 하 십시오.예 를 들 어 입력:1,2,4 출력 결 과 는 다음 과 같다.
[1]
[2]
[4]
[1, 2]
[1, 4]
[2, 4]
[1, 2, 4]
알 아야 할 것:공 집 은 모든 집합의 부분 집합 이다.진짜 부분 집합 은 부분 집합 을 포함 하지 않 는 집합 입 니 다.빈 부분 집합 이 아니면 부분 집합 과 빈 집합 을 포함 하지 않 습 니 다.
문제 풀이 방향:
이 문 제 는'비트 대응 법'으로 계산 할 수 있다.
예 를 들 어 집합 A={a,b,c}은 임의의 요소 에 대해 모든 하위 에 집중 하거나 존재 하지 않 습 니 다.부분 집합 으로 비 추기:
(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)->@(@빈 집합 표시)
상기 규칙 을 관찰 하면 컴퓨터 에 있 는 데이터 저장 방식 과 비슷 하기 때문에 하나의 정형 수 와 집합 매 핑 을 통 해...000~111.111(있 음,없 음,반대로 도 가능 함 을 나타 낸다).이 정형 수 를 통 해 한 번 씩 증가 하면 모든 수 를 얻 을 수 있다.즉,집합 에 해당 하 는 부분 집합 을 얻 을 수 있다.
주로 변위 연산 과 논리 적 사고력 을 고찰 하 는데 구체 적 인 코드 는 다음 과 같다(본 기계 의 진실 한 인증 을 거 쳐 절대적 으로 신뢰 할 수 있다).

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

주:2017-02-08 10:01:32  상기 코드 는 일정한 구멍 이 있 습 니 다.즉,중복 숫자 를 입력 할 때 결 과 는 중복 부분 집합 출력 이 있 고 제목 의 요 구 를 만족 시 키 지 못 합 니 다.부분 집합 을 계산 할 때 HashSet 를 넣 어 배열 해 야 합 니 다.최종 인쇄 결 과 는 sets 에서 얻 으 면 됩 니 다.구체 적 인 수정 내용 은 다음 그림 과 같 습 니 다.
1.주 함수 가 인쇄 된 곳 에서 받 은 반환 값 을 HashSet 형식 으로 수정 합 니 다.

2.함수 부분 에 서 는 패 키 징 목록 을 list 에서 set 로 변경 해 야 합 니 다.

이로써 수정 이 완료 되 었 습 니 다.테스트 실행 결 과 는 다음 과 같 습 니 다.

분석 코드 를 통 해 알 수 있 는 시간 복잡 도 는 O(n*log2n)이다.
코드 다운로드 주소:
https://github.com/liang68/interview
이상 은 본 고의 모든 내용 입 니 다.본 고의 내용 이 여러분 의 학습 이나 업무 에 어느 정도 도움 이 되 기 를 바 랍 니 다.또한 저 희 를 많이 지지 해 주시 기 바 랍 니 다!