Hatena::Grouptopcoder

TopCoder戦記

研究開発者・ellerのTopCoder挑戦記録。言語は主にJavaを使用しています。ドキュメンテーションコメントはSubmit完了後、ブログ掲載前に補完したものです。

2009-08-31SRM433 DIV2

IterableなJava版next_permutation

| 22:00

C++ライブラリであるSTLに実装されているnext_permutationをJavaのIterable<int[]>に置き換えて実装したもの。以下のようなコードで簡単に利用することができます。

for(int[] permutation : new Permutation(3)) {
	System.out.println(Arrays.toString(permutation));
}
/* 出力結果:
	[0, 1, 2]
	[0, 2, 1]
	[1, 0, 2]
	[1, 2, 0]
	[2, 0, 1]
	[2, 1, 0] */

アルゴリズムはSRM433のTopSubmissionや、Googleによる検索結果を参考(ほぼ流用)にさせていただきました。先駆者の方々に感謝致します。

import java.util.Iterator;

/**
 * <p>順列を表すクラス。反復子によって順列を表すint型配列を生成・取得する。
 * @author eller
 */
// 若干まぎらわしいがPermutationListなどの命名がベターか。
public class Permutation implements Iterable<int[]> {
	private final int size;

	/**
	 * <p>順列を表すクラスのコンストラクタ。反復子が返す配列の要素数を指定する。
	 * @param size 順列の要素数(10程度が妥当な最大値)
	 * @throws IllegalArgumentException 引数(順列の要素数)が0以下の場合
	 */
	public Permutation(int size) {
		if (size <= 0) throw new IllegalArgumentException();
		this.size = size;
	}

	public Iterator<int[]> iterator() {
		return new Iter(size);
	}

	private class Iter implements Iterator<int[]> {
		private final int[] source;
		private boolean isFirst = true;

		private Iter(int size) {
			source = new int[size];
			for(int i = 0; i < size; ++i) {
				source[i] = i;
			}
		}

		/**
		 * <p>反復子がまだ順列を返しうるか調べる。
		 * 本メソッドは{@link Iter#next()}呼び出し前に必ず1回ずつ実行する必要がある。
		 * @return 順列が存在する場合はtrue
		 */
		public boolean hasNext() {
			if (isFirst) {
				isFirst = false;
				return true;
			}

			int n = source.length;
			for (int i = n - 1; i > 0; i--) {
				if (source[i - 1] < source[i]) {
					int j = n;
					while (source[i - 1] >= source[--j]);
					swap(source, i - 1, j);
					reverse(source, i, n);
					return true;
				}
			}
			reverse(source, 0, n);
			return false;
		}

		/**
		 * <p>次の順列を表すint型配列を返す。
		 * <p>このメソッドが返す参照は常に同じ配列に対する参照である。
		 * このため配列の要素を変更したり次回の{@link Iter#next()}呼び出し後も参照する場合は、
		 * クラスの呼び出し側が配列のクローンを生成して利用する必要がある。
		 * @return 順列を表すint型配列
		 */
		public int[] next() {
			return source;
		}

		public void remove() {
			throw new UnsupportedOperationException();
		}

		private void swap(int[] is, int i, int j) {
			int t = is[i];
			is[i] = is[j];
			is[j] = t;
		}

		private void reverse(int[] is, int s, int t) {
			while (s < --t) swap(is, s++, t);
		}
	}
}