組合せ
組合せとは、いくつかの要素の集まりからいくつかの要素を選び出す方法です。
例えば、n個の要素{ a[0] , a[1] , a[2] , ... , a[n-1] }からk個選んだ組み合わせをすべて知りたいとするなら、
次のプログラムでnとkとa[0],a[1]...a[n-1]を入力すると組み合わせを漏れや重複なく出力してくれます。
例えば、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 ); } }
...