CODEWITHSUNDEEP
c++
chesschi
chesschi

Reputation: 708

String manipulation with permutation

Given that a string can vary from 2 to 7 characters. I need to fill * to make it up to 7 characters and store all the permutations to a container. In addition, it cannot accept three or more continuous * (e.g. ABCD*** won't be pushed to the container). Also the order of the characters cannot be changed.

For example, a string 'ABCDEF' filled with '*' could have the following permutations:

ABCDEF*
ABCDE*F
ABCD*EF
ABC*DEF
AB*CDEF
A*BCDEF
*ABCDEF

A string 'ABCD' filled with '*' could have the following permutations (note: ABCD*** not accepted because it has 3 continuous '*'):

ABC*D**
ABC**D*
AB*CD**
AB*C*D*
AB*C**D
...
**A*BCD

(...total 30 items will be pushed to the container)

I try to write a program to do this. If the string are 2 characters long, I need to loop 2 times. For example,

void loop_two_times(const std::string & str = "AB")
{
    for (int i = 0; i < 7; i++)
    {
        for (int j = i+1; j < 7; j++)
        {
            std::string ustring = get7StarsString(); // this string will contain 7 stars
            ustring[i] = str[0];
            ustring[j] = str[1];

            if (!tooMuchStars(ustring))
            {
                permutations.push_back(ustring);
            }
            else {} // do nothing
        }
    }
}

If the string are N characters long, I need to loop N times. However, I do not want to check the number of characters and write the functions to loop 2,3,4,5,6 times. e.g.

switch (numOfChars)
{
    case 2: loop_two_times(); break;
    case 3: loop_three_times(); break;
    case 4: loop_four_times(); break;
    case 5: loop_five_times(); break;
    case 6: loop_six_times(); break;
}

Please could you kindly suggest how can I implement this efficently?

Many thanks!

Upvotes: 3

Views: 138

Answers (1)

Jarod42
Jarod42

Reputation: 218323

You may use the following: (https://ideone.com/L209jH)

// return a string with '0' replaced with letter, and '1' with '*'.
std::string convert(const std::string& order, const std::string& s)
{
    std::string res;
    std::size_t pos = 0;
    for (std::size_t i = 0; i != order.size(); ++i) {
        if (order[i] == '1') {
            res += '*';
        } else {
            res += s[pos++];
        }
    }
    return res;
}

void print_combinaison(const std::string& msg)
{
    std::string s(msg.size(), '0');
    s.resize(7, '1');
    // s is a string of 7 letter with '0' (representing letter)
    // and '1' representing '*'
    // initial value of s is one of 0000000, 0000001, 0000011, 0000111,
    // 0001111, 0011111, 0111111 or 1111111.
    do
    {
        if (s.find("111") != std::string::npos) continue;

        std::cout << convert(s, msg) << std::endl;
    } while (std::next_permutation(begin(s), end(s)));
}

Upvotes: 2

Related Questions