Java에서 집합의 전원 집합을 효율적으로 생성하는 방법은 무엇입니까?

Java에서 집합의 거듭제곱 집합 생성

집합의 거듭제곱 집합은 해당 집합의 모든 하위 집합의 집합입니다. 예를 들어, {1, 2, 3}의 거듭제곱 집합은 다음과 같습니다.

{{}, {2}, {3}, {2, 3}, {1, 2}, {1, 3} , {1, 2, 3}, {1}}

세트가 있다고 가정합니다. Java:

Set<Integer> mySet = new HashSet<Integer>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
Set<Set<Integer>> powerSet = getPowerset(mySet);

최적의 시간 복잡도를 갖는 getPowerset 함수를 어떻게 작성할 수 있습니까?

해결책

powerset 함수의 시간 복잡도 O(2^n)입니다. 여기서 n은 집합의 요소 수입니다. 이는 n 요소가 있는 집합의 powerset에 2^n 하위 집합이 포함되어 있기 때문입니다.

다음은 제네릭과 집합을 사용하여 getPowerset 함수를 구현하는 작업입니다.

public static <T> Set<Set<T>> powerSet(Set<T> originalSet) {
    Set<Set<T>> sets = new HashSet<Set<T>>();
    if (originalSet.isEmpty()) {
        sets.add(new HashSet<T>());
        return sets;
    }
    List<T> list = new ArrayList<T>(originalSet);
    T head = list.get(0);
    Set<T> rest = new HashSet<T>(list.subList(1, list.size())); 
    for (Set<T> set : powerSet(rest)) {
        Set<T> newSet = new HashSet<T>();
        newSet.add(head);
        newSet.addAll(set);
        sets.add(newSet);
        sets.add(set);
    }       
    return sets;
}  

테스트

주어진 예제를 사용하여 getPowerset 함수를 테스트해 보겠습니다. 입력:

Set<Integer> mySet = new HashSet<Integer>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
for (Set<Integer> s : powerSet(mySet)) {
     System.out.println(s);
}

다음 출력이 인쇄됩니다.

[]
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]

위 내용은 Java에서 집합의 전원 집합을 효율적으로 생성하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!