Print combinations of a string from left to right (not permutation) c++

Question

Given a string, I want to print all the combinations, picking letters from left to right: Ex. Input: abcd Output: abc acd abd bcd ac ad bc bd cd

I can do it, but i cannot generalize it, for ex. in the string abcd, i can get all the mentioned combinations by deleting only one letter. Then I can do it also by deleting two letters and so on. code:

name = "abcdefghi";

//Deleting 2 letters

for(int i = 1; i < name.size(); i++){ 

    for(int k = 2; k < name.size(); k++){ 

        for(int j = 0; j < name.size(); j++){ // PRINT ARRAY
            if(j != i && j != k) cout << name[j];
        }
        cout << endl;

      }

  }

// Deleting 1 letter:

for(int i = 1; i < name.size(); i++){ 

        for(int j = 0; j < name.size(); j++){ // PRINT ARRAY
            if(j != i) cout << name[j];
        }
        cout << endl;  

  }

How can I generalize it so that I can first print the combination with 1 letter missing, then 2 letters missing, then 3, and so on... Because if I keep going like this, to get all the combinations with the number of letters missing from 1 to n, I will need n number of for loops...

So you don't want the combinations with all letters too? Do you want to start from -1characters? — koleygr, Jun 20 '17 at 21:24
A simple answer in your question is to put your loop in another loop who will remove letters... you can start by removing one or by removing zero chars — koleygr, Jun 20 '17 at 21:26
Possible duplicate of [creating all possible k combinations of n items in C++](https://stackoverflow.com/questions/12991758/creating-all-possible-k-combinations-of-n-items-in-c) — ljeabmreosn, Jun 20 '17 at 21:27
@koleygr I want the combinations which will keep the original order of letters unchanged. ex: input = abc i do not want "bca" or "bac" or "cab" or "ba" as an output — boogieman, Jun 20 '17 at 21:29

score 0 · Answer 1 · answered Jun 20 '17 at 23:05

You can do it like this for example:

print_combinations(const string& name) {
    if(name.size() > 1) {
        for(int i = 0; i < name.size(); ++i) {
            string name2 = name;
            name2.erase(i, 1);
            cout << name2;
        }
        for(int i = 0; i < name.size(); ++i) {
            string name2 = name;
            name2.erase(i, 1);
            print_combinations(name2);
        }
    }
}

score 0 · Answer 2 · answered Jun 20 '17 at 23:31

Currently, you can use a counter and use it as flag, something like:

void print_combinations(const std::string& s)
{
    if (s.size() >= 32) {
        return; // String too long
    }
    std::uint32_t end = 1u << s.size();
    for (std::uint32_t i = 0; i != end; ++i)
    {
        auto j = i;
        for (const auto c : s)
        {
            if ((j & 1) != 0) {
                std::cout << c;
            }
            j >>= 1;   
        }
        std::cout << std::endl;
    }
}

Demo

Print combinations of a string from left to right (not permutation) c++

2 Answers2