Permutation: Javaでの順列組合せの列挙

順列を全部生成するコードを書く必要があって世の中のコードを探したのだけど、あまりきれいなコードがなかったので自分で書いた、単なる備忘録的記事。
まあ、このコードがきれいかというと、うーん、でも使いやすさとシンプルさでは、いろいろ検索した中ではきれいだと思うんだけど。

public class Permutation<T extends <Serializable> {

  private int baseIndex;
  private int index;
  private T[] objs;

  private Permutation<T> subPermutation;

  public Permutation(T[] objs) {
    this(0, 0, objs.clone());
  }

  private Permutation(int baseIndex, int index, T[] objs) {
    if (objs == null || objs.length == 0) {
      throw new IllegalArgumentException();
    }

    this.baseIndex = baseIndex;
    this.index = index;
    this.objs = objs;

    if (this.index < this.objs.length - 1) {
      this.subPermutation =
        new Permutation<T>(this.baseIndex + 1, this.index + 1, this.objs);
    }
  }

  public T[] getTarget() {
    return this.objs;
  }

  public boolean next() {
    if (this.subPermutation == null) {
      return false;
    }

    boolean result = this.subPermutation.next();
    if (result == true) {
      return true;
    }

    this.swap(this.baseIndex, this.index);

    ++this.index;
    if (this.objs.length <= this.index) {
      this.index = this.baseIndex;
      return false;
    }

    this.swap(this.index, this.baseIndex);
    return true;
  }

  @Override
  public String toString() {
    // snip.
  }

  private void swap(int index1, int index2) {
    T tmp = this.objs[index1];
    this.objs[index1] = this.objs[index2];
    this.objs[index2] = tmp;
  }
}

呼び出し方は、

Permutation<String> p = new Permutation<>(new String[] { "a", "b", "c" });
do {
  System.out.println(p.toString());
} while (p.next());

で、次のようになる。

[a,b,c]
[a,c,b]
[b,a,c]
[b,c,a]
[c,b,a]
[c,a,b]

メモリも大して食わないし、そこそこ高速だと思う。