algorithm

@Harry He의 아이디어를 기반으로 다른 솔루션을 생각해 냈습니다. 아마도 가장 우아하지는 않지만 내가 이해하는대로 여기에 있습니다.

SP (S) = {{1}, {2}, {3}}의 고전적인 간단한 예제 PowerSet을 보겠습니다. 부분 집합의 수를 구하는 공식은 2 ^ n (7 + 빈 집합)입니다. 이 예에서는 2 ^ 3 = 8 개의 하위 집합입니다.

각 부분 집합을 찾으려면 아래 변환 표에 표시된 10 진수 0-7을 이진 표현으로 변환해야합니다.

행 단위로 테이블을 탐색하면 각 행은 하위 집합이되고 각 하위 집합의 값은 활성화 된 비트에서 나옵니다.

Bin Value 섹션의 각 열은 원래 입력 Set의 인덱스 위치에 해당합니다.

여기 내 코드 :

public class PowerSet {

/**
 * @param args
 */
public static void main(String[] args) {
    PowerSet ps = new PowerSet();
    Set<Integer> set = new HashSet<Integer>();
    set.add(1);
    set.add(2);
    set.add(3);
    for (Set<Integer> s : ps.powerSet(set)) {
        System.out.println(s);
    }
}

public Set<Set<Integer>> powerSet(Set<Integer> originalSet) {
    // Original set size e.g. 3
    int size = originalSet.size();
    // Number of subsets 2^n, e.g 2^3 = 8
    int numberOfSubSets = (int) Math.pow(2, size);
    Set<Set<Integer>> sets = new HashSet<Set<Integer>>();
    ArrayList<Integer> originalList = new ArrayList<Integer>(originalSet);
    for (int i = 0; i < numberOfSubSets; i++) {
        // Get binary representation of this index e.g. 010 = 2 for n = 3
        String bin = getPaddedBinString(i, size);
        //Get sub-set
        Set<Integer> set = getSet(bin, originalList));
        sets.add(set);
    }
    return sets;
}

//Gets a sub-set based on the binary representation. E.g. for 010 where n = 3 it will bring a new Set with value 2
private Set<Integer> getSet(String bin, List<Integer> origValues){
    Set<Integer> result = new HashSet<Integer>();
    for(int i = bin.length()-1; i >= 0; i--){
        //Only get sub-sets where bool flag is on
        if(bin.charAt(i) == '1'){
            int val = origValues.get(i);
            result.add(val);
        }
    }
    return result;
}

//Converts an int to Bin and adds left padding to zero's based on size
private String getPaddedBinString(int i, int size) {
    String bin = Integer.toBinaryString(i);
    bin = String.format("%0" + size + "d", Integer.parseInt(bin));
    return bin;
}

}