c++ - 如何只打印字符串的唯一排列？

Question

此函数打印字符串的排列，如何修改它以使其仅打印唯一的排列？“没有重复”

void RecPermute(string soFar, string rest) {
  if (rest == "")           // No more characters
    cout << soFar << endl;  // Print the word
  else                      // Still more chars
    // For each remaining char
    for (int i = 0; i < rest.length(); i++) {
      string next = soFar + rest[i];  // Glue next char
      string remaining = rest.substr(0, i) + rest.substr(i + 1);
      RecPermute(next, remaining);
    }
}
// "wrapper" function
void ListPermutations(string s) {
  RecPermute("", s);

标签： c++stringpermutation

Answer 1

std::next_permutation您可以使用创建独特排列的标准函数。

例子：

#include <algorithm>
#include <iostream>
#include <string>

void ListPermutations(std::string str) {
    std::sort(str.begin(), str.end()); // sort to start at the first permutation

    do {
        std::cout << str << '\n';

        // get the next unique permutation:
    } while( std::next_permutation(str.begin(), str.end()) );
}

int main() {
    ListPermutations("aaba");
}

输出：

aaab
aaba
abaa
baaa