의 powerset {1, 2, 3}
은 다음과 같습니다.
{{}, {2}, {3}, {2, 3}, {1, 2}, {1, 3}, {1, 2, 3}, {1}}
내가 Set
Java에 있다고 가정 해 봅시다 .
Set<Integer> mySet = new HashSet<Integer>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
Set<Set<Integer>> powerSet = getPowerset(mySet);
가능한 가장 복잡한 순서로 getPowerset 함수를 어떻게 작성합니까? (O (2 ^ n)일지도 모르겠네요.)
답변
예, 가능한 조합 O(2^n)
을 생성해야하기 때문에 실제로 그렇습니다 2^n
. 다음은 제네릭 및 세트를 사용하는 작업 구현입니다.
public static <T> Set<Set<T>> powerSet(Set<T> originalSet) {
Set<Set<T>> sets = new HashSet<Set<T>>();
if (originalSet.isEmpty()) {
sets.add(new HashSet<T>());
return sets;
}
List<T> list = new ArrayList<T>(originalSet);
T head = list.get(0);
Set<T> rest = new HashSet<T>(list.subList(1, list.size()));
for (Set<T> set : powerSet(rest)) {
Set<T> newSet = new HashSet<T>();
newSet.add(head);
newSet.addAll(set);
sets.add(newSet);
sets.add(set);
}
return sets;
}
예제 입력이 주어진 경우 테스트 :
Set<Integer> mySet = new HashSet<Integer>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
for (Set<Integer> s : SetUtils.powerSet(mySet)) {
System.out.println(s);
}
답변
사실, 저는 O (1)에서 당신이 요구하는 것을하는 코드를 작성했습니다. 문제는 당신이 계획 무엇을 할 다음 설정으로. 그냥 전화를 걸면 size()
O (1)이되지만 반복하려면 분명히O(2^n)
.
contains()
될 것이다 O(n)
등 .
정말 필요한가요?
편집하다:
이 코드는 이제 Guava 에서 사용할 수 있으며 메서드를 통해 노출됩니다 Sets.powerSet(set)
.
답변
여기에 발전기를 사용하는 솔루션이 있습니다. 장점은 전체 전력 세트가 한 번에 저장되지 않는다는 것입니다. 따라서 메모리에 저장할 필요없이 하나씩 반복 할 수 있습니다. 더 나은 옵션이라고 생각하고 싶습니다 … 복잡성은 동일합니다. O (2 ^ n), 그러나 메모리 요구 사항은 감소합니다 (가비지 수집기가 작동한다고 가정하면!;)).
/**
*
*/
package org.mechaevil.util.Algorithms;
import java.util.BitSet;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;
/**
* @author st0le
*
*/
public class PowerSet<E> implements Iterator<Set<E>>,Iterable<Set<E>>{
private E[] arr = null;
private BitSet bset = null;
@SuppressWarnings("unchecked")
public PowerSet(Set<E> set)
{
arr = (E[])set.toArray();
bset = new BitSet(arr.length + 1);
}
@Override
public boolean hasNext() {
return !bset.get(arr.length);
}
@Override
public Set<E> next() {
Set<E> returnSet = new TreeSet<E>();
for(int i = 0; i < arr.length; i++)
{
if(bset.get(i))
returnSet.add(arr[i]);
}
//increment bset
for(int i = 0; i < bset.size(); i++)
{
if(!bset.get(i))
{
bset.set(i);
break;
}else
bset.clear(i);
}
return returnSet;
}
@Override
public void remove() {
throw new UnsupportedOperationException("Not Supported!");
}
@Override
public Iterator<Set<E>> iterator() {
return this;
}
}
이를 호출하려면 다음 패턴을 사용하십시오.
Set<Character> set = new TreeSet<Character> ();
for(int i = 0; i < 5; i++)
set.add((char) (i + 'A'));
PowerSet<Character> pset = new PowerSet<Character>(set);
for(Set<Character> s:pset)
{
System.out.println(s);
}
내 프로젝트 오일러 라이브러리에서 가져온 것입니다 … 🙂
답변
어쨌든 전력 세트를 구성하려고 시도하는 메모리가 부족하기 때문에 (반복기 구현을 사용하지 않는 한) 합리적인 가정 인 n <63이면 이것은 더 간결한 방법입니다. 바이너리 연산은 Math.pow()
마스크 배열 보다 훨씬 빠르지 만 , 자바 사용자는이를 두려워합니다.
List<T> list = new ArrayList<T>(originalSet);
int n = list.size();
Set<Set<T>> powerSet = new HashSet<Set<T>>();
for( long i = 0; i < (1 << n); i++) {
Set<T> element = new HashSet<T>();
for( int j = 0; j < n; j++ )
if( (i >> j) % 2 == 1 ) element.add(list.get(j));
powerSet.add(element);
}
return powerSet;
답변
다음 은 코드를 포함하여 원하는 것을 정확히 설명하는 자습서입니다. 복잡성이 O (2 ^ n)이라는 점에서 맞습니다.
답변
@Harry He의 아이디어를 기반으로 다른 솔루션을 생각해 냈습니다. 아마도 가장 우아하지는 않지만 내가 이해하는대로 여기에 있습니다.
SP (S) = {{1}, {2}, {3}}의 고전적인 간단한 예제 PowerSet을 보겠습니다. 부분 집합의 수를 구하는 공식은 2 ^ n (7 + 빈 집합)입니다. 이 예에서는 2 ^ 3 = 8 개의 하위 집합입니다.
각 부분 집합을 찾으려면 아래 변환 표에 표시된 10 진수 0-7을 이진 표현으로 변환해야합니다.
행 단위로 테이블을 탐색하면 각 행은 하위 집합이되고 각 하위 집합의 값은 활성화 된 비트에서 나옵니다.
Bin Value 섹션의 각 열은 원래 입력 Set의 인덱스 위치에 해당합니다.
여기 내 코드 :
public class PowerSet {
/**
* @param args
*/
public static void main(String[] args) {
PowerSet ps = new PowerSet();
Set<Integer> set = new HashSet<Integer>();
set.add(1);
set.add(2);
set.add(3);
for (Set<Integer> s : ps.powerSet(set)) {
System.out.println(s);
}
}
public Set<Set<Integer>> powerSet(Set<Integer> originalSet) {
// Original set size e.g. 3
int size = originalSet.size();
// Number of subsets 2^n, e.g 2^3 = 8
int numberOfSubSets = (int) Math.pow(2, size);
Set<Set<Integer>> sets = new HashSet<Set<Integer>>();
ArrayList<Integer> originalList = new ArrayList<Integer>(originalSet);
for (int i = 0; i < numberOfSubSets; i++) {
// Get binary representation of this index e.g. 010 = 2 for n = 3
String bin = getPaddedBinString(i, size);
//Get sub-set
Set<Integer> set = getSet(bin, originalList));
sets.add(set);
}
return sets;
}
//Gets a sub-set based on the binary representation. E.g. for 010 where n = 3 it will bring a new Set with value 2
private Set<Integer> getSet(String bin, List<Integer> origValues){
Set<Integer> result = new HashSet<Integer>();
for(int i = bin.length()-1; i >= 0; i--){
//Only get sub-sets where bool flag is on
if(bin.charAt(i) == '1'){
int val = origValues.get(i);
result.add(val);
}
}
return result;
}
//Converts an int to Bin and adds left padding to zero's based on size
private String getPaddedBinString(int i, int size) {
String bin = Integer.toBinaryString(i);
bin = String.format("%0" + size + "d", Integer.parseInt(bin));
return bin;
}
}
답변
당신이 사용하는 경우 이클립스 컬렉션 (구 GS 컬렉션 ), 당신은 사용할 수있는 powerSet()
모든 SetIterables에 방법을.
MutableSet<Integer> set = UnifiedSet.newSetWith(1, 2, 3);
System.out.println("powerSet = " + set.powerSet());
// prints: powerSet = [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
참고 : 저는 Eclipse Collections의 커미터입니다.