Every possible combination of string

Question

I have to get every possible combination of given string. The string I get can be of various sizes but always contains only 1 and 0.

For example, Combinations I want to get with "101" as the input :

"000" "001" "010" "100" "110" "101" "011" "111".

I tried using std::next_permutation (c++20), I'm getting close but this not exactly not what I want.

The final goal is to store every combination inside a string vector.

Below is what I tried with next_permutation

// I'm not using *using namespace std* no need to mention it
std::vector<std::string>    generate_all_combinations(std::string base)
{
   std::vector<std::string> combinations;
   do {
       combinations.push_back(base);
   } while (std::next_permutation(base.begin(), base.end()));
   return combinations;
}

When I print the vector's content I have : "011" "101" "110".

The base strings "000" and "111" are not a problem I can generate those pretty easily. But I'm still lacking other combinations like "001" "010" "100".

Are you looking for a built-in function, or no? Also, why would you need an input if it always returns that same thing? Might just be me. — cs1349459, May 17 '22 at 13:06
start with an all zero string, `"0000"`, then replace one of the `0`'s with a `1`, call `next_permutation` until you've cycled through all permutations, repeate. — NathanOliver, May 17 '22 at 13:06
Not particularly no, just seeking help that's all. That was just an example. The string always contains zeros and ones but can be of various sizes. I need to be able to generate every possible one and zero combinations for every given string length. — arlaine, May 17 '22 at 13:07
Do you know how to add 1 to a binary number with pen and paper? — user253751, May 17 '22 at 13:10
I'll actually go ahead and mention the fact that you aren't `using namespace std`. It's better not to use it, so well done, keep on doing so. — ChemiCalChems, May 17 '22 at 13:11
@paolo not really, I don't have any time or memory usage constraints either — arlaine, May 17 '22 at 13:12
@NathanOliver your solution seems to be working ! I'm trying things out to make just to make sure but it seems good ! — arlaine, May 17 '22 at 13:13
If you start with 00000000 and keep adding 1 until you get to 11111111, that's all 8-character combinations of 0 and 1. — user253751, May 17 '22 at 13:14
To paraphrase a bit: *"When I [start with `"011"`and] print the vector's content I have [all permutations involving two `1`s and one `0`]. The strings [with all `0`s and all `1`s] are not a problem I can generate those pretty easily. But I'm still lacking [all permutations of one `1` and two `0`s]."*-- which is how permutations work. — JaMiT, May 17 '22 at 13:16
@ArminMontigny It's exactly what the OP is looking for. ("Combinations", "Permutations", and "the input" confuse the situation, but look at their exact request.) — Sneftel, May 17 '22 at 14:57

score 0 · Answer 1 · 2022-05-17T13:32:06.970

0

Maybe this is not the answer you expect, but if you want every binary combination for a specified count of bits, this is one possible solution:

  void getCombinations(std::vector<std::string>& str_list, int len)
  {
    uint64_t comb_count = 1ull << len;

    std::string str;

    for(uint64_t i = 0; i < comb_count; ++i) {

      str.clear();

      for(int j = 0; j < len; ++j)
        str += ((i >> j) & 0x1) ? "1" : "0";

      str_list.push_back(str);
    }
  }

edited May 17 '22 at 13:32

answered May 17 '22 at 13:21

1

You should not use `pow` to calculate the integer power of 2. `1ull << len` is better. – mch May 17 '22 at 13:30

Stack Danny · Answer 2 · 2022-05-17T13:49:44.440

std::next_permutation won't work here, you will have to craft your own function here.

For example, for a symbol list "ab" where the permutations have a length of 3, you can get the 4th permutation by converting the number 4 to base 2 (length of symbol list) and use that as an index table for your permutation.

so 4 becomes 100 in base 2, so the indices are {1, 0, 0} and for the symbol list that is 'b', 'a', 'a' therefore the string "baa".

Here is a possible implementation of this, and it takes a symbol list, permutation length and current number of permutation. You can manually convert to any base by diving by base^position and taking modulus of base. The base is simply the length of the symbol list:

template<std::integral T>
constexpr T int_pow(T b, T e) {
    return (e == 0) ? T{ 1 } : b * int_pow(b, e - 1);
}

std::string get_permutation(const std::string& symbols, std::size_t permutation_size, std::size_t position) {
    std::string permutation;
    permutation.resize(permutation_size);

    auto base = symbols.length();

    for (std::size_t i = 0u; i < permutation_size; ++i) {

        auto index = (position / int_pow(base, i)) % base;
        permutation[permutation_size - i - 1] = symbols[index];
    }
    return permutation;
}

so calling this:

std::cout << get_permutation("ab", 3u, 4u) << '\n';

prints out

baa

with this function you can make a list_permutations function, that adds all permutations to a vector:

std::vector<std::string> list_permutations(const std::string& symbols, std::size_t permutation_size) {

    auto result_size = std::size_t(std::pow(symbols.length(), permutation_size));
    std::vector<std::string> result(result_size);

    for (std::size_t i = 0u; i < result.size(); ++i) {
        result[i] = get_permutation(symbols, permutation_size, i);
    }

    return result;
}

int main() {
    auto list = list_permutations("01", 3u);
    for (auto& i : list) {
        std::cout << i << '\n';
    }
}

output:

You should avoid using `std::pow` to compute integer powers. `std::pow` converts to a floating point type which could lead to an off by on error due to floating point imprecision. — NathanOliver, May 17 '22 at 13:33
@NathanOliver is `std::powl` a correct way to do it? or does one have to implement the own integer pow. — Stack Danny, May 17 '22 at 13:41
`powl` also using floating point math. It is recomended to either make your own or find on you can use. There is an implementation here: https://stackoverflow.com/questions/15851636/why-is-my-integer-math-with-stdpow-giving-the-wrong-answer — NathanOliver, May 17 '22 at 13:45

Every possible combination of string

2 Answers2