java - 生成一组对象的所有组合

Question

我在这里遇到一个问题，我需要生成所有可能的对象组合并将它们存储在列表中以供稍后分析..

Internet 上的搜索包括许多算法，这些算法无法满足存储组合的要求。大多数常见的搜索只是通过打印出来来生成组合列表，而其他搜索只处理字符串，而不是对象。

一些算法使用位来表示不同的组合，但这种解决方案最多只能限制 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();
  }
}