「組合せ」の編集履歴（バックアップ）一覧はこちら

組合せ - (2012/02/09 (木) 21:42:33) の１つ前との変更点

追加された行は緑色になります。

削除された行は赤色になります。

*組み合わせ

組み合わせは、icpcにおいて非常に重要です。
組み合わせとは、いくつかの要素の集まりからいくつかの要素を選び出す方法です。
例えば、n個の要素{ 0 , 1 , 2 , ... , n-1 }からk個選んだ組み合わせをすべて知りたいとするなら、
次のプログラムでnとkを入力すると組み合わせを漏れや重複なく出力してくれます。
 #include <iostream>
 #include <vector>
 using namespace std;
 typedef vector<int> comb;
 
 inline int first(int n){
 	return ((1 << n) - 1);
 }
 
 inline int nextSet(int x){
 	int small, ripple, newSmall,ones;
 	
 	small = x & -x;
 	ripple = x + small;
 	newSmall = ripple & -ripple;
 	ones = (( newSmall / small ) >> 1) - 1;
 	
 	return (ripple | ones);
 }
 
 comb setComb(int s, int n){
 	comb c;
 	for(int i=0 ; i<n ; i++){
 		if( s & 1) c.push_back(i);
 		s >>= 1;
  	}
 	return c;
 }
 
 int main(){
 	int n, k, x;
 	comb c;
 	 
 	cin >> n >> k; 
 	x = first(k);
 	while( !(x & ~first(n) ) ){
 		c = setComb( x , n );
 		for(int i=0 ; i<c.size() ; i++){
 			cout << c.at(i);
 			(i==c.size()-1)? cout << endl : cout << ","; 
 		}
 		x = nextSet( x );
 	}
 }
 
このプログラムを少し改良するだけでn個の要素{ a[0] , a[1] , ... , a[n-1]}からk個選ぶ組み合わせ
という汎用的なパターンにも対応できるプログラムにできるので考えてみてください。











...