組合せ - 秋田大学ICPC対策室@wiki

組合せ

組合せとは、いくつかの要素の集まりからいくつかの要素を選び出す方法です。
例えば、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 );
	}
}

...