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

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

Patricia Arquette
풀어 주다: 2024-12-03 19:05:14
원래의
500명이 탐색했습니다.

How Can I Efficiently Calculate the Powerset of a Set in 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

원천:php.cn
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
저자별 최신 기사
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿