题目描述

 输入一个可能含有重复字符的字符串，打印出该字符串中所有字符的全排列。

输入

单组测试数据，输入数据是一个长度不超过10个字符的字符串，以逗号结尾。

输出

打印出该字符串中所有字符的全排列。以字典序顺序输出，用空格分隔。

样例输入

abc,

样例输出

abc acb bac bca cab cba

算法描述

本题先将输入的字符串按字典序排好序，然后从字符串首位置开始递归查找下一个位置开始所有可能的全排列，若遇到相同字符则跳过此次递归，直到遍历到字符串最后一个元素为止。为保证以字典序输出，每次在查找从下一个位置开始的全排列之前，需要将现位置后边的字符按字典序排好序。

C++代码

#include <iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
void perm(vector<char> a, int k, int m)
{
    if (k == m)
    {
        for (int i = 0; i <= m; i++)
            cout << a[i];
        cout << ' ';
    }
    else
    {
        char* s = new char[m - k];
        int top = k + 1;
        for (int l = 0; l < m - k; l++)
            s[l++] = a[top++];
        sort(a.begin() + k + 1, a.end());
        perm(a, k + 1, m);
        top = k + 1;
        for (int l = 0; l < m - k; l++)
            a[top++]=s[l++];
        for (int i = k+1; i <= m; i++)
        {
            if (a[i] == a[i-1])
                continue;
            int t = a[i];
            a[i] = a[k];
            a[k] = t;
            int top1 = k + 1;
            for (int l1 = 0; l1 < m - k; l1++)
                s[l1++] = a[top1++];
            sort(a.begin() + k + 1, a.end());
            perm(a, k + 1, m);
            top1 = k + 1;
            for (int l1 = 0; l1 < m - k; l1++)
                a[top1++] = s[l1++];
            t = a[i];
            a[i] = a[k];
            a[k] = t;
        }
    }
}
int main()
{
    char h[20];
    cin.getline(h, ',');
    vector<char>a;
    for (int i = 0; i < 20; i++)
    {
        if (h[i] == ',')break;
        a.push_back(h[i]);
    }
    if (a.size() == 0)return 0;
    sort(a.begin(), a.end());
    perm(a, 0, a.size() - 1);
    return 0;
}