-1

ここで問題が発生し、オブジェクトの可能なすべての組み合わせを生成し、後で分析するためにそれらをリストに保存する必要があります。

インターネットでの検索には、組み合わせを保存するというこの要件を満たしていない多くのアルゴリズムが含まれています。最も一般的な検索では、組み合わせのリストを印刷するだけで生成されますが、他の検索では、オブジェクトではなく文字列のみを処理します。

一部のアルゴリズムはビットを使用してさまざまな組み合わせを表しますが、このソリューションは最大32個のオブジェクトに制限されているため、十分ではありません。

全体として、可能なすべての組み合わせ(べき集合)を生成し、オブジェクト(32以上)を処理し、組み合わせを印刷するだけでなく、これらの組み合わせをリストに格納できるアルゴリズムを探しています。アレイ。

4

1 に答える 1

1

すべての組み合わせを一度に 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();
  }
}
于 2013-01-25T13:09:58.760 に答える