在C ++中实现排列，组合和PowerSet [英] Implementation of Permutation, Combinations and PowerSet in C++

问题描述

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

I am looking for the implementation of Permutation, Combination and PowerSet using C+++

推荐答案

使用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 。如果在编译时已知大小，则优选 std :: bitset< N> over std :: vector< bool>

Note that if the size if less than the number of bit of your integer, you may you that integer instead of vector<bool>. If the size is known at compile time, prefer std::bitset<N> over 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));
}

实例

这篇关于在C ++中实现排列，组合和PowerSet的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！