Java에서 세트의 Powerset을 효율적으로 계산하는 방법은 무엇입니까?

Java의 집합에 대한 Powerset 계산

컴퓨터 과학에서 집합의 Powerset은 해당 집합의 가능한 모든 하위 집합의 모음을 나타냅니다. 이 기사에서는 최적의 시간 복잡도를 위해 노력하면서 Java에서 정수 집합의 파워셋을 구성하는 방법을 살펴봅니다.

문제 설명

Java에서 정의된 정수 집합이 주어졌습니다. , 우리의 목표는 powerset을 계산하는 getPowerset 함수를 만드는 것입니다. 우리는 이 함수에 대해 가능한 최고의 시간 복잡도를 달성하는 것을 목표로 합니다.

해결책

파워셋 계산의 시간 복잡도는 실제로 O(2^n)입니다. 여기서 n은 원래 세트의 크기입니다. 아래 함수는 제네릭과 집합을 활용하여 powerset 계산을 효율적으로 구현합니다.

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;
}

Test

다음 코드는 예제 입력을 사용하여 함수를 보여줍니다.

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

출력

질문에 제공된 테스트 출력은 {1, 2, 3}의 거듭제곱 집합을 표시합니다.

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

일반 및 재귀를 사용하여 getPowerset 함수를 구현하여 O의 최적 시간 복잡도를 달성합니다. (2^n) 및 Java에서 집합의 파워셋을 계산하기 위한 효율적인 솔루션입니다.

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