Java에서 집합의 거듭제곱 집합을 효율적으로 계산하려면 어떻게 해야 합니까?

Java의 Powerset 이해

집합의 거듭제곱 집합은 빈 집합과 원래 집합을 포함하여 해당 요소의 가능한 모든 하위 집합을 나타냅니다. 그 자체. n개의 요소를 포함하는 집합의 경우 해당 powerset은 2^n개의 고유 하위 집합으로 구성됩니다.

효율적으로 Powerset 얻기

Java에서는 다음을 계산하는 getPowerset 함수를 정의할 수 있습니다. 주어진 세트의 파워셋. 이 작업의 최적 시간 복잡도는 O(2^n)입니다. 여기서 n은 입력 집합의 요소 수입니다.

일반 및 재귀를 사용한 구현

다음 구현에서는 제네릭을 활용하여 모든 유형의 집합에 대해 작업합니다.

public static <T> Set<Set<T>> powerSet(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 : powerSet(rest)) {
        Set<T> newSet = new HashSet<>();
        newSet.add(head);
        newSet.addAll(set);
        sets.add(newSet);
        sets.add(set);
    }
    return sets;
}

사용법 및 예

이 함수를 사용하려면 세트를 인스턴스화하고 이를 getPowerset에 인수로 전달합니다. 예를 들어 다음 입력 예를 사용하면

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

이렇게 하면 주어진 세트의 파워 세트가 예상되는 형식으로 인쇄됩니다.

위 내용은 Java에서 집합의 거듭제곱 집합을 효율적으로 계산하려면 어떻게 해야 합니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!