Реализация подстановок, комбинаций и POWERSET в C++

Question

Я ищу для осуществления перестановочного, комбинации и POWERSET с использованием C+++

Answer 1

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

using namespace std; 

void 
Permutation(vector <char>set, vector <char>path, vector <bool> visited) 
{ 
    if (set.size() == path.size()) { 
     copy(path.begin(), path.end(), ostream_iterator <char>(cout, " ")); 
     cout << endl; 
     return; 
    } 
    for (size_t i = 0; i < set.size(); ++i) { 
     if (!visited[i]) { 
      visited[i] = true; 
      path.push_back(set[i]); 
      Permutation(set, path, visited); 
      visited[i] = false; 
      path.pop_back(); 
     } 
    } 
} 

void 
Combination(vector <char>set, vector <char>path, size_t start, size_t maxlen) 
{ 
    if (maxlen == path.size()) { 
     copy(path.begin(), path.end(), ostream_iterator <char>(cout, " ")); 
     cout << endl; 
     return; 
    } 
    for (size_t i = start; i < set.size(); ++i) { 
     path.push_back(set[i]); 
     Combination(set, path, ++start, maxlen); 
     path.pop_back(); 
    } 
} 

void 
PowerSet(vector <char>set) 
{ 
    for (int i = 0; i <= set.size(); ++i) { 
     vector <char>path; 
     Combination(set, path, 0, i); 
    } 
} 

int 
main() 
{ 
    vector <char>vc { 
     'A', 'B', 'C', 'D' 
    }; 
    vector <char>path; 
    vector <bool> visited(4, false); 
    cout << "\n------PERMUTATION----------\n"; 
    Permutation(vc, path, visited); 
    cout << "\n------COMBINATION----------\n"; 
    Combination(vc, path, 0, 3); 
    cout << "\n------POWERSET-------------\n"; 
    PowerSet(vc); 
    return 0; 
} 

Answer 2

Использование STL:

перестановку:

с помощью std::next_permutation

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())); 
} 

POWERSET:

Обратите внимание, что если размер если меньше, чем количество бит вашего числа, вы можете вам, что целое число вместо vector<bool>. Если размер известно во время компиляции, предпочитают std::bitset<N> над std::vector<bool>

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)); 
} 

Live example