Every possible combination of string [duplicate]

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".

Answer 1

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

Answer 2

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:

000
001
010
011
100
101
110
111