C++ permutation generator

Question

I wrote this code to help with programming challenges. A lot of problems can be solved by complete search so I wrote this function that I can copy/paste between problems to generate permutations quickly. Does anyone have any comments or suggestions to improve this function?

bool bruteforceGenerator(string& permutationIn, const vector<char>& options, const int maxLength)
{
    if(permutationIn.size() == 0) // In case we begin with a blank string just return the starting case
    {
        permutationIn = options[0];
        return true;
    }
    else
    {
        // First try to increment any digit in the string starting from the right
        for(int i = permutationIn.size() - 1; i>=0; i--)
        {
            if(permutationIn[i] != options[options.size()-1]) // If we can increment any digit
            {
                // Increment the individual digit
                auto index = find(options.begin(), options.end(), permutationIn[i]);
                permutationIn[i] = *(index+1);
                // Set all the digits after i back to their start values
                for(int j = i+1; j<permutationIn.size(); j++)
                {
                    permutationIn[j] = options[0];
                }
                return true;
            }
        }

        if(permutationIn.size() < maxLength) // If we could not increment a digit perhaps we could still make the string longer
        {
            permutationIn.push_back(0);
            for(auto &i : permutationIn) i = options[0];
            return true;
        }
        else return false; // If we could not increment any digit and we could not make the string any longer then we are out of permutations
    }
}

The return type of the function was chosen to allow usage of the function to look something like

string permutation;
vector <char> options {'^','v','<','>'};
while(bruteforceGenerator(permutation, options, 2))
{
    // Do something with the permutation
}

Sample output:

^
v
<
>
^^
^v
^<
^>
v^
vv
v<
v>
<^
<v
<<
<>
>^
>v
><
>>

Size of powerset is 2^n, which is larger than n! permutations. You describe this as "permutations", but it's computing "powerset" (while suppressing null set). — J_H
– J_H, Commented Sep 18, 2017 at 0:03
I agree with @JH, a permutation in math is clearly an order that involves all the input elements. Here you may return smaller sets... FYI, the number of items in your resulting set is \$ c = |options|, \sum_{i=1}^{n=maxLength} c^i \$. — Alexis Wilke
– Alexis Wilke, Commented Sep 18, 2017 at 3:01

Alexis Wilke · Accepted Answer · 2017-09-18 01:46:34Z

A few things...

Parameter Name

bool bruteforceGenerator(string& permutationIn, ...

From what I can see, this is not an "In" parameter. It's an "InOut". It actually keeps track of the current state too.

Expressions and Spaces

for(int i = permutationIn.size() - 1; i>=0; i--)

Here I'm being picky. You have spaces around the i = ... - 1, but you lose them in the second expression: i>=0. I would suggest that you choose one or the other style. I prefer spaces because I think it makes it easier to read.

Blocks of code

else return false;

On this one, long term, I prefer to have a block like so:

else
{
    return false;
}

It's also a lot easier to not later make a mistake by adding a block after the else and forgetting to move the return false; statement. Also always having a block means you can add a second line of code and it will probably work as expected. Without the block, it probably won't work as expected. Note that applies to this statement as well:

for(auto &i : permutationIn) i = options[0];

Lighter/Clearer overall Function

Finally, as a whole, I would change the way the function if/else blocks are managed. I would actually not have an else and would have a return false; as the very last statement. There is sample skeleton:

if(condition)
{
    ...
    return true;
}

for(...;...;...)
{
    if(condition)
    {
        ...
        return true;
    }
}

if(condition)
{
    return true;
}

return false;

I think that makes it simpler to read. The cases that work are managed first and return true. If nothing works, we end up returning false.

There is a comment by @Incomputable about an std::next_permutation algorithm. I can see that your algorithm would not fit for two reasons:

The std::next_permutation requires you start with a sorted array of characters; and
It only computes permutations with a size equal to the input size when in your case you start with 1 character and grow up to maxlength which can be smaller than the input length (as in your example).

However, one interesting aspect of that algorithm is the fact that you can run through the permutations again after false is returned.

You could achieve that behavior by clearing the permutationIn variable just before returning false:

    ...
    permutationIn.clear();
    return false;
}

Of course, the pattern you have is similar to reading a file. Once the EOF is found, further reading continues to give you EOF. Either pattern has its merits...

Stack Exchange Network

C++ permutation generator

1 Answer 1

You must log in to answer this question.

Hot Network Questions

C++ permutation generator

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions