c++ - C++中置换、组合和PowerSet的实现

Question

我正在寻找使用 C++ 实现 Permutation、Combination 和 PowerSet

Answer 1

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

电源组：

请注意，如果大小小于整数的位数，则可以使用该整数而不是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));
}

活生生的例子

Answer 2

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