/* title
  POWER SET
*/

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

  ¦C¦L¬Y§Ç¦Cªº POWER SET

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

#include <iostream>
#include <iterator>
#include <list>
#include <vector>
#include <algorithm>

using namespace std ;


template <class T , class Iter>
void  find_subset( Iter first , Iter last , int n , vector<T>& foo ) {

    if ( n == 0 ) {

        cout << "( " ;
        copy( foo.begin() , foo.end() , ostream_iterator<T>(cout," ") ) ;
        cout << ")  " ;
        
    } else {
        
        for ( Iter iter = first ; iter != last ; ++iter ) {

            foo.push_back( *iter ) ;
            ++iter ;
            find_subset( iter , last , n-1 , foo ) ;
            --iter ;
            foo.pop_back() ;

        }

    }

}


template <class T , class Iter>
void  power_set( Iter first , Iter last ) {
    
    int  no = distance(first,last) ;

    cout << "The POWER SET of ( " ;
    copy( first , last , ostream_iterator<T>(cout," ") ) ;
    cout << ")\n" ;
    
    cout << "> £X" << endl << endl ;

    vector<T>  sets ;
    for ( int i = 1 ; i <= no ; ++i ) {
        sets.resize(0) ;
        cout << "> " << i << " element" << ( i == 1 ? " :\n" : "s :\n" ) ;
        find_subset( first , last , i , sets ) ;
        cout << "\n\n" ;
    }

    cout << endl ;

}


int main() {

    char  a[] = "abcdefg" ;
    power_set<char,char*>( a , a+6 ) ;

    int   b[] = { 1 , 2 , 3 , 4 };
    power_set<int,int*>( b , b+4 ) ;

    list<char>  c(a+2,a+5) ;
    power_set<char,list<char>::iterator>( c.begin() , c.end() ) ;

    return 0 ;
    
}

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

The POWER SET of ( a b c d e f )
> £X

> 1 element :
( a )  ( b )  ( c )  ( d )  ( e )  ( f )  

> 2 elements :
( a b )  ( a c )  ( a d )  ( a e )  ( a f )  ( b c )  ( b d )  ( b e )  ( b f )  ( c d )  ( c e )  ( c f )  ( d e )  ( d f )  ( e f )  

> 3 elements :
( a b c )  ( a b d )  ( a b e )  ( a b f )  ( a c d )  ( a c e )  ( a c f )  ( a d e )  ( a d f )  ( a e f )  ( b c d )  ( b c e )  ( b c f )  ( b d e )  ( b d f )  ( b e f )  ( c d e )  ( c d f )  ( c e f )  ( d e f )  

> 4 elements :
( a b c d )  ( a b c e )  ( a b c f )  ( a b d e )  ( a b d f )  ( a b e f )  ( a c d e )  ( a c d f )  ( a c e f )  ( a d e f )  ( b c d e )  ( b c d f )  ( b c e f )  ( b d e f )  ( c d e f )  

> 5 elements :
( a b c d e )  ( a b c d f )  ( a b c e f )  ( a b d e f )  ( a c d e f )  ( b c d e f )  

> 6 elements :
( a b c d e f )  


The POWER SET of ( 1 2 3 4 )
> £X

> 1 element :
( 1 )  ( 2 )  ( 3 )  ( 4 )  

> 2 elements :
( 1 2 )  ( 1 3 )  ( 1 4 )  ( 2 3 )  ( 2 4 )  ( 3 4 )  

> 3 elements :
( 1 2 3 )  ( 1 2 4 )  ( 1 3 4 )  ( 2 3 4 )  

> 4 elements :
( 1 2 3 4 )  


The POWER SET of ( c d e )
> £X

> 1 element :
( c )  ( d )  ( e )  

> 2 elements :
( c d )  ( c e )  ( d e )  

> 3 elements :
( c d e )  

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