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