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

「組合せ」(2012/02/09 (木) 21:51:04) の最新版変更点

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

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

*組合せ

組合せとは、いくつかの要素の集まりからいくつかの要素を選び出す方法です。
例えば、n個の要素{ a[0] , a[1] , a[2] , ... , a[n-1] }からk個選んだ組み合わせをすべて知りたいとするなら、
次のプログラムでnとkを入力すると組み合わせを漏れや重複なく出力してくれます。
 #include <iostream>
 #include <vector>
 using namespace std;
 
 int first(int n){
 	return ((1 << n) - 1);
 }
 
 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);
 }
 
 vector<int> setComb(int s, int n){
 	vector<int> c;
 	for(int i=0 ; i < n ; i++){
 		if( s & 1 ) c.push_back( a[i] );
 		s >>= 1;
  	}
 	return c;
 }
 
 int main(){
 	int n, k, x;
 	vector<int> a, c;
 	 
 	cin >> n >> k; 
 	for(int i=0 ; i < n ; i++ ){
 		cin >> a[i];
 	}
 	x = first(k);
 	while( !(x & ~first(n) ) ){
 		c = setComb( x , n );
 		for(int i=0 ; i < c.size() ; i++){
 			cout << c[i];
 			( i == c.size()-1 )? cout << endl : cout << ","; 
 		}
 		x = nextSet( x );
 	}
 }










...

*組合せ

組合せとは、いくつかの要素の集まりからいくつかの要素を選び出す方法です。
例えば、n個の要素{ a[0] , a[1] , a[2] , ... , a[n-1] }からk個選んだ組み合わせをすべて知りたいとするなら、
次のプログラムでnとkとa[0],a[1]...a[n-1]を入力すると組み合わせを漏れや重複なく出力してくれます。
 #include <iostream>
 #include <vector>
 using namespace std;
 
 int first(int n){
 	return ((1 << n) - 1);
 }
 
 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);
 }
 
 vector<int> setComb(int s, int n){
 	vector<int> c;
 	for(int i=0 ; i < n ; i++){
 		if( s & 1 ) c.push_back( a[i] );
 		s >>= 1;
  	}
 	return c;
 }
 
 int main(){
 	int n, k, x;
 	vector<int> a, c;
 	 
 	cin >> n >> k; 
 	for(int i=0 ; i < n ; i++ ){
 		cin >> a[i];
 	}
 	x = first(k);
 	while( !(x & ~first(n) ) ){
 		c = setComb( x , n );
 		for(int i=0 ; i < c.size() ; i++){
 			cout << c[i];
 			( i == c.size()-1 )? cout << endl : cout << ","; 
 		}
 		x = nextSet( x );
 	}
 }










...