fork download 
  1. // Jarod42
  2.  
  3. #include <algorithm>
  4. #include <cassert>
  5. #include <iostream>
  6. #include <iterator>
  7. #include <vector>
  8.  
  9. template <typename T>
  10. void Permutation(std::vector<T> v)
  11. {
  12.     std::sort(v.begin(), v.end());
  13.     do {
  14.         std::copy(v.begin(), v.end(), std::ostream_iterator<T>(std::cout, " "));
  15.         std::cout << std::endl;
  16.     } while (std::next_permutation(v.begin(), v.end()));
  17. }
  18.  
  19. template <typename T>
  20. void Combination(const std::vector<T>& v, std::size_t count)
  21. {
  22.     assert(count <= v.size());
  23.     std::vector<bool> bitset(count, 1);
  24.     bitset.resize(v.size(), 0);
  25.  
  26.     do {
  27.         for (std::size_t i = 0; i != v.size(); ++i) {
  28.             if (bitset[i]) {
  29.                 std::cout << v[i] << " ";
  30.             }
  31.         }
  32.         std::cout << std::endl;
  33.     } while (std::prev_permutation(bitset.begin(), bitset.end()));
  34. }
  35.  
  36. bool increase(std::vector<bool>& bs)
  37. {
  38.     for (std::size_t i = 0; i != bs.size(); ++i) {
  39.         bs[i] = !bs[i];
  40.         if (bs[i] == true) {
  41.             return true;
  42.         }
  43.     }
  44.     return false; // overflow
  45. }
  46.  
  47. template <typename T>
  48. void PowerSet(const std::vector<T>& v)
  49. {
  50.     std::vector<bool> bitset(v.size());
  51.  
  52.     do {
  53.         for (std::size_t i = 0; i != v.size(); ++i) {
  54.             if (bitset[i]) {
  55.                 std::cout << v[i] << " ";
  56.             }
  57.         }
  58.         std::cout << std::endl;
  59.     } while (increase(bitset));
  60. }
  61.  
  62. int main()
  63. {
  64.     std::vector<char> vc{ 'A', 'B', 'C', 'D' };
  65.     std::vector<char> path;
  66.     std::vector<bool> visited(4, false);
  67.     std::cout << "\n------PERMUTATION----------\n";
  68.     Permutation(vc);
  69.     std::cout << "\n------COMBINATION----------\n";
  70.     Combination(vc, 3);
  71.     std::cout << "\n------POWERSET-------------\n";
  72.     PowerSet(vc);
  73.     return 0;
  74. }
  75.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin 
Standard input is empty
stdout 
------PERMUTATION----------
A B C D 
A B D C 
A C B D 
A C D B 
A D B C 
A D C B 
B A C D 
B A D C 
B C A D 
B C D A 
B D A C 
B D C A 
C A B D 
C A D B 
C B A D 
C B D A 
C D A B 
C D B A 
D A B C 
D A C B 
D B A C 
D B C A 
D C A B 
D C B A 

------COMBINATION----------
A B C 
A B D 
A C D 
B C D 

------POWERSET-------------

A 
B 
A B 
C 
A C 
B C 
A B C 
D 
A D 
B D 
A B D 
C D 
A C D 
B C D 
A B C D
https://ideone.com/LV8UqB
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!