Для генерации всех комбинаций множества объектов

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