/* title
   樂透包牌
 */

/* comment ************************************************************

  由 42 個樂透號碼中, 隨機選 n >= 6 個號碼, 
  印出由此 n 個號碼中所有可能的樂透號碼組合

***********************************************************************/

#include <iostream>
#include <iomanip>
#include <set>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cstdlib>
#include <ctime>


using namespace std ;

void  list_combination( const vector<int>& a , const int max_no , 
                        const int count , set<int>& s , bool& new_shuffle ) {
    
    if ( s.size() == max_no ) {
        static  int c  ;
        if ( new_shuffle ) {
            c = 1 ;
            new_shuffle = false ;
        }
        cout << setw(3) << c++ << " : (" ;
        for( set<int>::iterator i = s.begin() ; i != s.end() ; ++i ) cout << setw(3) << *i ;
        cout << " )" << endl ;
    } else {
        for ( int i = count ; i < a.size() ; ++i ) {
            s.insert( a[i] ) ;
            list_combination(a,max_no,i+1,s,new_shuffle) ;
            s.erase( a[i] ) ;
        }
    }

}


int random_no( int n ) {   return  rand() % n ;  }



int main() {
    
    int  i , n , N = 42 ;

    vector<int>  no(N) ;
    for ( i = 0 ; i < N ; ++i )  no[i] = i + 1 ;

    set<int>     s ;

    srand( static_cast<unsigned int>(time(NULL)) ) ;
    
    bool  new_shuffle ;
    
    while ( 1 ) {
        
        cout << "> 輸入包牌張數 : " ;
        cin >> n ;
        if ( n >= 6 && n <= N ) {

            new_shuffle = true ;
            random_shuffle(no.begin(),no.end(),random_no) ;

            sort( no.begin() , no.begin()+n ) ;

            cout << "> " ;
            copy( no.begin() , no.begin()+n , ostream_iterator<int>(cout," ") ) ;
            cout << endl ;

            list_combination(vector<int>(no.begin(),no.begin()+n),6,0,s,new_shuffle) ;
            cout << endl ;

        }
    
    }
    
    return 0 ;
    
}


/*********************************************************************************
  OUTPUT  OUTPUT  OUTPUT  OUTPUT  OUTPUT  OUTPUT  OUTPUT  OUTPUT  OUTPUT  OUTPUT 
 *********************************************************************************

> 輸入包牌張數 : 7
> 1 8 13 18 26 27 30 
  1 : (  1  8 13 18 26 27 )
  2 : (  1  8 13 18 26 30 )
  3 : (  1  8 13 18 27 30 )
  4 : (  1  8 13 26 27 30 )
  5 : (  1  8 18 26 27 30 )
  6 : (  1 13 18 26 27 30 )
  7 : (  8 13 18 26 27 30 )

> 輸入包牌張數 : 8
> 1 3 6 11 13 21 29 30 
  1 : (  1  3  6 11 13 21 )
  2 : (  1  3  6 11 13 29 )
  3 : (  1  3  6 11 13 30 )
  4 : (  1  3  6 11 21 29 )
  5 : (  1  3  6 11 21 30 )
  6 : (  1  3  6 11 29 30 )
  7 : (  1  3  6 13 21 29 )
  8 : (  1  3  6 13 21 30 )
  9 : (  1  3  6 13 29 30 )
 10 : (  1  3  6 21 29 30 )
 11 : (  1  3 11 13 21 29 )
 12 : (  1  3 11 13 21 30 )
 13 : (  1  3 11 13 29 30 )
 14 : (  1  3 11 21 29 30 )
 15 : (  1  3 13 21 29 30 )
 16 : (  1  6 11 13 21 29 )
 17 : (  1  6 11 13 21 30 )
 18 : (  1  6 11 13 29 30 )
 19 : (  1  6 11 21 29 30 )
 20 : (  1  6 13 21 29 30 )
 21 : (  1 11 13 21 29 30 )
 22 : (  3  6 11 13 21 29 )
 23 : (  3  6 11 13 21 30 )
 24 : (  3  6 11 13 29 30 )
 25 : (  3  6 11 21 29 30 )
 26 : (  3  6 13 21 29 30 )
 27 : (  3 11 13 21 29 30 )
 28 : (  6 11 13 21 29 30 )

> 輸入包牌張數 : 7
> 4 23 30 36 37 39 40 
  1 : (  4 23 30 36 37 39 )
  2 : (  4 23 30 36 37 40 )
  3 : (  4 23 30 36 39 40 )
  4 : (  4 23 30 37 39 40 )
  5 : (  4 23 36 37 39 40 )
  6 : (  4 30 36 37 39 40 )
  7 : ( 23 30 36 37 39 40 )

 *********************************************************************************/