create powerset of set given in a vector

Here is an algorithm that calculates the powerset of a set of elements given in a vector input of length n. A vector bit that will be used to select subsets is created and it’s elements are initialized with 1. Then for each subset size up to n/2 (outer loop) a element of bit is switched from 1 to 0 (This way the vector is already sorted what is handy for the use of std::next_permutation). Then the inner loop is entered which creates 2 subsets. The first consists of items in input where those items are selected, that have the same index as those which contain a 1 in bit. The other subset consists of items in input where the counterpart in bit contains 0. The subsets are added to the result. Then std::next_permuation is called on bit creating the next permutation. The process is repeated until bit is in sorted order again, which signals that all permutations have been used. The last condition in the inner loop avoids adding subsets twice in case the input has even length.

template<typename T>
std::vector<std::vector<T>> powerset(std::vector<T> const&amp; input){
    std::vector<std::vector<T>> rv{};
    if(!input.empty()){
        rv.push_back(input);
    }   
    rv.push_back({});
    std::size_t input_size = input.size();
    std::vector bit(input.size(),1);
    bool even = (input_size % 2 == 0) ? true : false;
    std::size_t split_point = input_size/2;
    for(std::size_t i = 0; i < split_point; ++i){
        bit[i]=0;
        do {
            std::vector tmp1;
            tmp1.reserve(i+1);
            std::vector tmp2;
            tmp2.reserve(input_size-(i+1));
            for(std::size_t j = 0; j < input.size(); ++j){
                if(bit[j]){
                    tmp1.push_back(input[j]);
                } else {
                    tmp2.push_back(input[j]);
                }   
            }   
 
            rv.push_back(std::move(tmp1));
            if(!((i == split_point-1) &amp;&amp; even)){
                rv.push_back(std::move(tmp2));
            }   
        } while (std::next_permutation(bit.begin(),bit.end()));
    }   
    return rv;
}

Leave a Reply

Your email address will not be published. Required fields are marked *