// Jarod42
#include <algorithm>
#include <cassert>
#include <iostream>
#include <iterator>
#include <vector>
template < typename T>
void Permutation( std:: vector < T> v)
{
std:: sort ( v.begin ( ) , v.end ( ) ) ;
do {
std:: copy ( v.begin ( ) , v.end ( ) , std:: ostream_iterator < T> ( std:: cout , " " ) ) ;
std:: cout << std:: endl ;
} while ( std:: next_permutation ( v.begin ( ) , v.end ( ) ) ) ;
}
template < typename T>
void Combination( const std:: vector < T> & v, std:: size_t count)
{
assert ( count <= v.size ( ) ) ;
std:: vector < bool > bitset( v.size ( ) - count, 0 ) ;
bitset.resize ( v.size ( ) , 1 ) ;
do {
for ( std:: size_t i = 0 ; i ! = v.size ( ) ; ++ i) {
if ( bitset[ i] ) {
std:: cout << v[ i] << " " ;
}
}
std:: cout << std:: endl ;
} while ( std:: next_permutation ( bitset.begin ( ) , bitset.end ( ) ) ) ;
}
bool increase( std:: vector < bool > & bs)
{
for ( std:: size_t i = 0 ; i ! = bs.size ( ) ; ++ i) {
bs[ i] = ! bs[ i] ;
if ( bs[ i] == true ) {
return true ;
}
}
return false ; // overflow
}
template < typename T>
void PowerSet( const std:: vector < T> & v)
{
std:: vector < bool > bitset( v.size ( ) ) ;
do {
for ( std:: size_t i = 0 ; i ! = v.size ( ) ; ++ i) {
if ( bitset[ i] ) {
std:: cout << v[ i] << " " ;
}
}
std:: cout << std:: endl ;
} while ( increase( bitset) ) ;
}
int main( )
{
std:: vector < char > vc{ 'A' , 'B' , 'C' , 'D' } ;
std:: vector < char > path;
std:: vector < bool > visited( 4 , false ) ;
std:: cout << "\n ------PERMUTATION----------\n " ;
Permutation( vc) ;
std:: cout << "\n ------COMBINATION----------\n " ;
Combination( vc, 3 ) ;
std:: cout << "\n ------POWERSET-------------\n " ;
PowerSet( vc) ;
return 0 ;
}
Ly8gSmFyb2Q0MgoKI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGNhc3NlcnQ+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPGl0ZXJhdG9yPgojaW5jbHVkZSA8dmVjdG9yPgoKdGVtcGxhdGUgPHR5cGVuYW1lIFQ+CnZvaWQgUGVybXV0YXRpb24oc3RkOjp2ZWN0b3I8VD4gdikKewogICAgc3RkOjpzb3J0KHYuYmVnaW4oKSwgdi5lbmQoKSk7CiAgICBkbyB7CiAgICAgICAgc3RkOjpjb3B5KHYuYmVnaW4oKSwgdi5lbmQoKSwgc3RkOjpvc3RyZWFtX2l0ZXJhdG9yPFQ+KHN0ZDo6Y291dCwgIiAiKSk7CiAgICAgICAgc3RkOjpjb3V0IDw8IHN0ZDo6ZW5kbDsKICAgIH0gd2hpbGUgKHN0ZDo6bmV4dF9wZXJtdXRhdGlvbih2LmJlZ2luKCksIHYuZW5kKCkpKTsKfQoKdGVtcGxhdGUgPHR5cGVuYW1lIFQ+CnZvaWQgQ29tYmluYXRpb24oY29uc3Qgc3RkOjp2ZWN0b3I8VD4mIHYsIHN0ZDo6c2l6ZV90IGNvdW50KQp7CiAgICBhc3NlcnQoY291bnQgPD0gdi5zaXplKCkpOwogICAgc3RkOjp2ZWN0b3I8Ym9vbD4gYml0c2V0KHYuc2l6ZSgpIC0gY291bnQsIDApOwogICAgYml0c2V0LnJlc2l6ZSh2LnNpemUoKSwgMSk7CgogICAgZG8gewogICAgICAgIGZvciAoc3RkOjpzaXplX3QgaSA9IDA7IGkgIT0gdi5zaXplKCk7ICsraSkgewogICAgICAgICAgICBpZiAoYml0c2V0W2ldKSB7CiAgICAgICAgICAgICAgICBzdGQ6OmNvdXQgPDwgdltpXSA8PCAiICI7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgc3RkOjpjb3V0IDw8IHN0ZDo6ZW5kbDsKICAgIH0gd2hpbGUgKHN0ZDo6bmV4dF9wZXJtdXRhdGlvbihiaXRzZXQuYmVnaW4oKSwgYml0c2V0LmVuZCgpKSk7Cn0KCmJvb2wgaW5jcmVhc2Uoc3RkOjp2ZWN0b3I8Ym9vbD4mIGJzKQp7CiAgICBmb3IgKHN0ZDo6c2l6ZV90IGkgPSAwOyBpICE9IGJzLnNpemUoKTsgKytpKSB7CiAgICAgICAgYnNbaV0gPSAhYnNbaV07CiAgICAgICAgaWYgKGJzW2ldID09IHRydWUpIHsKICAgICAgICAgICAgcmV0dXJuIHRydWU7CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIGZhbHNlOyAvLyBvdmVyZmxvdwp9Cgp0ZW1wbGF0ZSA8dHlwZW5hbWUgVD4Kdm9pZCBQb3dlclNldChjb25zdCBzdGQ6OnZlY3RvcjxUPiYgdikKewogICAgc3RkOjp2ZWN0b3I8Ym9vbD4gYml0c2V0KHYuc2l6ZSgpKTsKCiAgICBkbyB7CiAgICAgICAgZm9yIChzdGQ6OnNpemVfdCBpID0gMDsgaSAhPSB2LnNpemUoKTsgKytpKSB7CiAgICAgICAgICAgIGlmIChiaXRzZXRbaV0pIHsKICAgICAgICAgICAgICAgIHN0ZDo6Y291dCA8PCB2W2ldIDw8ICIgIjsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBzdGQ6OmNvdXQgPDwgc3RkOjplbmRsOwogICAgfSB3aGlsZSAoaW5jcmVhc2UoYml0c2V0KSk7Cn0KCmludCBtYWluKCkKewogICAgc3RkOjp2ZWN0b3I8Y2hhcj4gdmN7ICdBJywgJ0InLCAnQycsICdEJyB9OwogICAgc3RkOjp2ZWN0b3I8Y2hhcj4gcGF0aDsKICAgIHN0ZDo6dmVjdG9yPGJvb2w+IHZpc2l0ZWQoNCwgZmFsc2UpOwogICAgc3RkOjpjb3V0IDw8ICJcbi0tLS0tLVBFUk1VVEFUSU9OLS0tLS0tLS0tLVxuIjsKICAgIFBlcm11dGF0aW9uKHZjKTsKICAgIHN0ZDo6Y291dCA8PCAiXG4tLS0tLS1DT01CSU5BVElPTi0tLS0tLS0tLS1cbiI7CiAgICBDb21iaW5hdGlvbih2YywgMyk7CiAgICBzdGQ6OmNvdXQgPDwgIlxuLS0tLS0tUE9XRVJTRVQtLS0tLS0tLS0tLS0tXG4iOwogICAgUG93ZXJTZXQodmMpOwogICAgcmV0dXJuIDA7Cn0K