Pages

CodeEval string permutations

Given in input a string that could contains letters and numbers, we should output all its permutations comma separated and alphabetically ordered according to the usual conventions.

This is a CodeEval sponsored challenge, so I'll just write here a few hints and not the full solution.

There is a very useful C++ STL function that does all the job for us, namely std::next_permutation(). It assumes the collection it works on has been in the initial state, and it modifies it to the next permutation, until there is anything to permutate. When there is nothing more to do, it returns false.

So we would std::sort() our collection - that should be modifiable, and then std::next_permutation() it in a loop, storing the permutations in a temporary buffer, or maybe directly outputting it to standard output.
std::sort(s.begin(), s.end());
// ...
do {
  // ...
} while (std::next_permutation(s.begin(), s.end()));
The only minor nuisance left now is the comma. We should add it to each permutation but the last one. There are a number of ways to address this point, for instance you could see it in a different perspective. Each permutation has a comma before it, but the first one. Or maybe you could blissfully ignore the point when you build the solution, and simply remove the last character before returning your solution. If you are following this strategy, the C++11 pop_back() std::string method could be useful.

If pop_back() is not available yet on your compiler, here is an alternative solution:
s.erase(s.size() - 1, 1); // s.pop_back();
In any case you should remember to check the size of your input string. If it is empty or consisting of just one character there is nothing to do. Otherwise you are safe in assuming there is something you could erase in the resulting output.

No comments:

Post a Comment