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

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

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

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

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

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

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

public static <t> Set<set>> getPowerset(Set<t> originalSet) {
    Set<set>> 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;
}</t></t></t></t></set></t></set></t>

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

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

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

출력:

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

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