Java에서 집합의 Powerset을 효율적으로 생성하는 방법은 무엇입니까?

Java에서 Powerset 찾기: 효율적인 접근 방식

집합의 Powerset은 원래 집합의 가능한 모든 하위 집합을 포함합니다. 크기 n 집합의 경우 powerset에는 2^n 요소가 포함됩니다. Java에서는 효율적인 알고리즘을 사용하여 Powerset 생성을 처리하는 것이 일반적입니다.

예를 고려하세요.

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

이 설정을 사용하여 작업은 최적의 시간 복잡도로 mySet의 powerset을 생성하는 getPowerset 함수를 설계하는 것입니다.

최적 시간 복잡도: O (2^n)

언급했듯이 파워셋에는 2^n 요소가 포함되어 있습니다. 따라서 이러한 모든 요소를 ​​생성하려면 본질적으로 O(2^n) 시간 복잡성이 필요합니다.

구현

다음 코드는 일반적이고 효율적인 구현을 제공합니다.

공개 정적 설정> powerSet(Set 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;

}

예

앞서 제공된 예 활용:

세트<정수> mySet = new HashSet<>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
for (Set s : 파워셋(마이셋)) {

System.out.println(s);

}

출력은 다음과 같습니다.

{}
{1}
{2}
{1, 2}
{3}
{1, 3}
{2, 3}
{1, 2, 3}

이는 O(2^n) 시간 복잡도로 지정된 집합의 거듭제곱 집합을 생성하는 방법을 보여줍니다.

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