C++ all arrangements of a set of strings

Question

I am trying to generate all arrangements of strings in a vector. For example, for

vector<string> vs = { "a", "b", "c"};

I wrote the following code:

do{
    for (string s : vs)
        cout << s << " ";
    cout << endl;
} while (std::next_permutation(vs.begin(), vs.end()));

My output is:

a b c
a c b
b a c
b c a
c a b
c b a

but, I am missing the combinations like

a
a b
b a
c

etc..

I would like to modify my code so that includes these arrangements as well. How to do it? Thanks!

`a` is not a permutation of `a, b, c` so `std::next_permutation` itself won't be enough. But consider what happens when you generate every possible subset of `a, b, c` and then every permutation of each subset... Also, be aware that `while (std::next_permutation(...))` will only give you all permutations if the initial input is lexicographically sorted - it is in your example, but you should probably ensure this directly (`std::sort` or at least `std::is_sorted`). — Max Langhof, Jun 26 '19 at 08:22
Almost duplicate of https://stackoverflow.com/questions/9430568/generating-combinations-in-c — Evg, Jun 26 '19 at 08:23
fwiw `next_permutation` is about permutations, while you want combinations, see eg here for what is the difference https://betterexplained.com/articles/easy-permutations-and-combinations/ — 463035818_is_not_an_ai, Jun 26 '19 at 08:23
... well, no, actually i was wrong, as it seems you do not want combinations (where `a b` and `b a` are considered the same), but as Max wrote: You want all permutations of all subsets — 463035818_is_not_an_ai, Jun 26 '19 at 08:25
You want **power set**, I answered [there](https://stackoverflow.com/a/25556248/2684539). — Jarod42, Jun 26 '19 at 08:28

Jarod42 · Answer 1 · 2019-06-26T09:25:34.493

You might implement Power set with:

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

Demo

Then do permutation of each set, something like:

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, typename F>
void PowerSet(const std::vector<T>& v, F f)
{
    std::vector<bool> bitset(v.size());

    do {
        f(v, bitset);
    } while (increase(bitset));
}

template <typename T, typename F>
void AllArrangements(const std::vector<T>& v, F f)
{
    PowerSet(v, [f](const std::vector<T>& v, const std::vector<bool>& bitset){
        std::vector<T> toPermute;
        for (std::size_t i = 0; i != v.size(); ++i) {
            if (bitset[i]) {
                toPermute.push_back(v[i]);
            }
        }
        do {
            f(toPermute);
        } while (std::next_permutation(toPermute.begin(), toPermute.end()));
    });
}

Demo

This will not generate `a b` and `b a`. You need to also generate all permutations of each subset. — Max Langhof, Jun 26 '19 at 08:41
See also https://math.stackexchange.com/questions/158320/is-there-a-word-to-describe-the-set-of-permutations-of-each-member-of-the-powers, https://stackoverflow.com/questions/19079038/what-is-the-number-of-all-set-permutations-in-a-power-set, http://oeis.org/A000522 — Max Langhof, Jun 26 '19 at 08:47
@MaxLanghof: Indeed, I miss that OP want permutation of each set. fixed. — Jarod42, Jun 26 '19 at 09:26

score 2 · Accepted Answer · answered Jun 26 '19 at 09:16

Your example shows that you want to not only output each subset of your input (the Power set) but also all permutations of each set.

I am not aware of a particular term used for this, but OEIS A000522 calls these "arrangements".

To get what you need, you have to essentially combine your code with Jarod's partial answer (or any of the other power set implementations you can find around here):

void outputAllPermutations(std::vector<std::string> input)
{
    // assert(std::is_sorted(input.begin(), input.end()));
    do
    {
        for (std::string s : input)
            std::cout << s << " ";
        std::cout << std::endl;
    } while (std::next_permutation(input.begin(), input.end()));
}

bool isBitSet(unsigned bitset, std::size_t i)
{
    return (bitset & (1 << i)) != 0;
}

void outputAllArrangements(const std::vector<std::string>& input)
{
    // assert(std::is_sorted(input.begin(), input.end()));
    // assert(input.size() < std::sizeof(unsigned) * 8);

    unsigned bitset = 0;

    std::vector<std::string> subset{};
    subset.reserve(input.size());

    for (unsigned bitset = 0; bitset < (1 << input.size()); ++bitset)
    {
        subset.clear();
        for (std::size_t i = 0; i != input.size(); ++i)
            if (isBitSet(bitset, i))
                subset.push_back(input[i]);

        outputAllPermutations(subset);
    }
}

Demo including example output

I used an unsigned instead of std::vector<bool> as I find the overall incrementation logic much easier to reason about that way. This theoretically "limits" the code to inputs smaller than 32 strings (or 64, depending on platform), but seeing as input length 22 would already take thousands of years to output at 1 CPU cycle per output I am comfortable with that.

Note: in Wikipedia entry Permutation, this is mentioned as a generalization of *permutation* term. (see *Other uses of the term permutation* section). I am not aware of a more specific term — Damien, Jun 26 '19 at 09:26

C++ all arrangements of a set of strings

2 Answers2