Hatena::Grouptopcoder

TopCoder戦記

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

2009-09-29SRM427 DIV2

IterableなJava版next_combination(ビットフラグ版)

| 21:47

以前実装したIterableなJava版next_permutationと同じように、C++のnext_combinationJavaのIterable<Long>に置き換えて実装したもの。以下のようなコードで簡単に利用することができます。ビットフラグにはlong型を利用したため、最大で62個の組み合わせまで対応できます。

for (long l : new Combination(5, 3)) {
	String binaryString = String.format("%5s", Long.toBinaryString(l)).replace(' ', '0');
	System.out.println(binaryString);
}
/* 
 * RESULT:
 *   00111
 *   01011
 *   01101
 *   01110
 *   10011
 *   10101
 *   10110
 *   11001
 *   11010
 *   11100
 */

アルゴリズムは谷崎久志さんのウェブサイトにある「組み合わせを求めるプログラムについて」をJavaへ移植したものです。わかりやすい資料を公開してくださいまして、ありがとうございます。

// 2つのinner classをコピーして使用すること。
import java.util.Iterator;

public class CombTest {
	// SAMPLE
	public static void main(String[] args) {
		for (long l : new Combination(62, 2)) {
			String binaryString = String.format("%62s", Long.toBinaryString(l)).replace(' ', '0');
			System.out.println(binaryString);
		}
	}

	private static class Combination implements Iterable<Long> {
		private final int max;
		private final int select;
		
		public Combination(int max, int select) {
			if (max < 1 || 62 < max) {
				throw new IllegalArgumentException();
			}
			this.max = max;
			this.select = select;
		}
		@Override
		public Iterator<Long> iterator() {
			return new CombinationIterator(max, select);
		}
	}

	private static class CombinationIterator implements Iterator<Long> {
		private long value;
		private final long max;

		public CombinationIterator(int max, int select) {
			this.value = (1L << select) - 1L;
			this.max = 1L << max;
		}

		@Override
		public boolean hasNext() {
			return value < max;
		}

		@Override
		public Long next() {
			long stock = value;
			value = next(value);
			return stock;
		}

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

		private long next(long source) {
			long param1 = smallestBitOf(source);
			long param2 = param1 + source;
			long param3 = smallestBitOf(param2);
			long param5 = (param3 / param1) >>> 1;
			return param5 - 1 + param2;
		}

		private long smallestBitOf(long source) {
			long result = 1L;
			while (source % 2 == 0) {
				source >>>= 1;
				result <<= 1;
			}
			return result;
		}
	}
}

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