Java 세트의 전원 세트를 효율적으로 생성하는 방법은 무엇입니까?

Java에서 최적의 복잡성으로 집합의 Powerset 얻기

집합의 Powerset은 해당 집합의 모든 하위 집합의 모음입니다. n개의 요소가 있는 집합의 경우 powerset에는 2^n개의 하위 집합이 포함됩니다.

Java 집합을 고려해 보겠습니다.

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

getPowerset이라는 함수를 작성하여 다음의 powerset을 생성하려고 합니다. 이 세트. 이 작업의 이상적인 복잡성은 O(2^n)입니다.

Java의 제네릭과 집합을 사용하여 가능한 구현 중 하나는 다음과 같습니다.

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

    for (Set<T> set : getPowerset(rest)) {
        Set<T> newSet = new HashSet<>();
        newSet.add(head);
        newSet.addAll(set);
        sets.add(newSet);
        sets.add(set);
    }

    return sets;
}

이 재귀 솔루션은 집합의 요소를 반복합니다. 이를 각 하위 집합에 추가하고 새 하위 집합을 생성합니다. 나머지 요소의 전력 세트를 일관되게 유지합니다.

예제 입력을 사용한 간단한 테스트로 예상한 결과를 얻을 수 있습니다.

for (Set<Integer> s : getPowerset(mySet)) {
    System.out.println(s);
}

출력:

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

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