#include #include #include #include // the algorithm std::vector > combinations( const std::vector& data , uintmax_t z ){ std::vector > out; uintmax_t size = data.size(); std::vector counters; for ( uintmax_t i = 0 ; i < z ; ++ i ) counters.push_back( i ); do { std::vector comb; for ( uintmax_t i : counters ) comb.push_back( data[ i ] ); out.push_back( comb ); for ( uintmax_t i = z ; i-- ; ){ counters[ i ]++; if ( i < z - 1 ) for ( uintmax_t j = i ; j < z - 1 ; ++j ) counters[ j + 1 ] = counters[ j ] + 1; if ( counters[ i ] < size - ( z-i ) + 1 ) break ; } } while ( counters[ 0 ] != size - z + 1 ); return out; } // random data generator std::vector generate( uintmax_t z ){ srand( time( 0) ); std::vector out; for ( uintmax_t i = 0 ; i < z ; ++i ) out.push_back( rand()%10 ); return out; } // std::ostream overloads for std::vector #include std::ostream& operator <<( std::ostream& stream , const std::vector& data ){ stream << "[" ; for ( uintmax_t i = 0 ; i < data.size() ; ++i ){ if ( i ) stream << ", "; stream << data[ i ]; } stream << "]"; return stream ; } // helper function to run the algorithm on some data void f( std::vector data , int z ){ auto result = combinations( data , z ); std::cout << " combinations of size( " << z << " ) : ["; for ( auto combination : result ) std::cout << combination ; std::cout << "]" << std::endl ; } // helper function to generate tests void test( uintmax_t z ){ std::vector data = generate( z ); std::cout << " # Data : " << data << std::endl ; for ( uintmax_t i = 1 ; i <= z ; ++i ) f( data , i ); std::cout << std::endl; } using namespace std; int main() { cout << "Combination test with indexes values\n"; vector indexes = {0,1,2,3,4}; cout << indexes << endl; for ( uintmax_t i = 1 ; i <= indexes.size() ; ++i ) f( indexes , i ); cout << "\n\n * * * * * *\n\n"; cout << "Combination test with random values\n"; for ( uintmax_t i = 1 ; i < 10 ; ++i ) test( i ); return 0; }

@John Wells #Combinations