개체 집합의 모든 조합을 생성하려면

Question

개체의 가능한 모든 조합을 생성하고 나중에 분석 할 목록에 저장할 필요가있는 곳에서 여기에 문제가 있습니다.

인터넷에서의 검색에는 많은 알고리즘이 포함되어 있습니다 조합을 저장하는이 요구 사항에 미치지 못합니다. 가장 일반적인 검색은 단순히 인쇄하여 조합 목록을 생성하는 반면, 다른 검색은 객체가 아닌 문자열 만 처리합니다.

일부 알고리즘은 다양한 조합을 나타 내기 위해 비트를 사용하지만이 솔루션은 최대 32 개 개체로만 제한되며 이는 충분하지 않습니다.

전체적으로 가능한 모든 조합 (파워 세트)을 생성 할 수있는 알고리즘을 찾고 있는데, 오브젝트 (32 개 이상)를 처리하고 조합을 인쇄하는 것만이 아니라 이러한 조합을 저장하는 것 배열 목록에.

Answer 1

모든 조합을 한 번에 하나의 거대한 관리 할 수없는 배열로 생성하는 대신에 배열의 각 항목에 대해 생성기를 작성하므로 항목에 액세스하면 항목을 액세스하는 가상 배열이 생성됩니다. 항목을 즉시.

다음은 enum 반복기의 코드입니다. 다른 질문에서 그와 비슷한 것을 게시했습니다. Iterator을 구현하지만 내부적으로는 인덱스를 디코딩하고 인덱스의 비트 패턴에서 즉석에서 조합을 선택하여 각 조합을 생성합니다 (private Enum[] get(int x) 메서드 참조). 원하는 경우 인덱스에 BigInteger 또는 심지어 byte[]을 사용하도록 확장 할 수 있어야합니다.

public class EnumIterator implements Iterator<Enum[]> { 
    // The enum classes 
    private final Class<? extends Enum>[] enums; 
    // The pseudo-position in the list. 
    private int i = 0; 
    // The total entries in the list. 
    private final int N; 

    // Construct from classes. 
    private EnumIterator(Class<? extends Enum>... enums) { 
    // Grab the enums. 
    this.enums = enums; 
    // Work out the Max as the product of all sets of constants. 
    int max = 1; 
    for (int n = 0; n < enums.length; n++) { 
     max *= enums[n].getEnumConstants().length; 
    } 
    N = max; 
    } 

    // Get that one from the possibles. 
    private Enum[] get(int x) { 
    // Make new array. 
    Enum[] next = new Enum[enums.length]; 
    // Fill it with the ith entry. 
    for (int j = next.length - 1; j >= 0; j--) { 
     Enum[] e = enums[j].getEnumConstants(); 
     // Pick the right one from it. 
     next[j] = e[x % e.length]; 
     // Fold out that enum. 
     x /= e.length; 
    } 
    return next; 
    } 

    @Override 
    public boolean hasNext() { 
    return i < N; 
    } 

    @Override 
    public Enum[] next() { 
    if (hasNext()) { 
     return get(i++); 
    } else { 
     throw new NoSuchElementException(); 
    } 
    } 

    @Override 
    public void remove() { 
    throw new UnsupportedOperationException("Not supported."); 
    } 

    enum ABC { 
    A, B, C; 
    } 

    enum XY { 
    X, Y; 
    } 

    enum IJ { 
    I, J; 
    } 

    enum OneTwoThree { 
    ONE, TWO, THREE 
    } 

    private static void test() { 
    // Also works - but constructing from classes is cleaner. 
    //Iterator<Enum[]> i = new EnumIterator(ABC.values(), XY.values(), IJ.values()); 
    System.out.println("ABC x XY x IJ"); 
    for (Enum[] e : Iterables.in(new EnumIterator(ABC.class, XY.class, IJ.class))) { 
     System.out.println(Arrays.toString(e)); 
    } 
    System.out.println("ABC"); 
    for (Enum[] e : Iterables.in(new EnumIterator(ABC.class))) { 
     System.out.println(Arrays.toString(e)); 
    } 
    System.out.println("ABC x OneTwoThree"); 
    for (Enum[] e : Iterables.in(new EnumIterator(ABC.class, OneTwoThree.class))) { 
     System.out.println(Arrays.toString(e)); 
    } 
    System.out.println("MT"); 
    for (Enum[] e : Iterables.in(new EnumIterator())) { 
     System.out.println(Arrays.toString(e)); 
    } 
    } 

    public static void main(String args[]) { 
    test(); 
    } 
}