如何按排序顺序生成数组的所有排列？

Question

我有一个数组,用户可以插入一个字符串.

我有这个代码:

int main(){
  char anagrama[13];
  cin >> anagrama;
  for(int j = 0; j < strlen(anagrama); j++){
    cout << anagrama[j];
    for(int k = 0; k < strlen(anagrama); k++){
      if(j != k)
        cout << anagrama[k];
    }
    cout << endl;
  }
}

问题是我需要按排序顺序排列字符串的所有排列.

例如,如果用户写:abc,输出必须是:

abc
acb
bac
bca
cab
cba

并且我的代码没有显示所有排列,也没有排序

你能帮助我吗？

我需要在没有已经实现的功能的情况下进行实现.

我认为有一个递归函数,但我不知道如何.

这是一个例子:http: //www.disfrutalasmatematicas.com/combinatoria/combinaciones-permutaciones-calculadora.html 没有重复和排序

Answer 1

在C++中,您可以使用std::next_permutation逐个进行排列.std::next_permutation在第一次调用之前,您需要按字母顺序对字符进行排序:

cin>>anagrama;
int len = strlen(anagrama);
sort(anagrama, anagrama+len);
do {
    cout << anagrama << endl;
} while (next_permutation(anagrama, anagrama+len));

这是关于ideone的演示.

如果你必须自己实现的排列,你可以借用的源代码中next_permutation,或选择递归实现置换算法的一个简单的方法.

Answer 2

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

using namespace std;

void permute(string select, string remain){
    if(remain == ""){
        cout << select << endl;
        return;
    }
    for(int i=0;remain[i];++i){
        string wk(remain);
        permute(select + remain[i], wk.erase(i, 1));
    }
}

int main(){
    string anagrama;
    cout << "input character set >";
    cin >> anagrama;
    sort(anagrama.begin(), anagrama.end());
    permute("", anagrama);
}

另一个版本

#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <algorithm>

using namespace std;

void permute(string& list, int level, vector<string>& v){
    if(level == list.size()){
        v.push_back(list);
        return;
    }
    for(int i=level;list[i];++i){
        swap(list[level], list[i]);
        permute(list, level + 1, v);
        swap(list[level], list[i]);
    }
}

int main(){
    string anagrama;
    vector<string> v;
    cout << "input character set >";
    cin >> anagrama;
    permute(anagrama, 0, v);
    sort(v.begin(), v.end());
    copy(v.begin(), v.end(), ostream_iterator<string>(cout, "\n"));
}