牛客网机试题：全排列

全排列

题目描述

给定一个由不同的小写字母组成的字符串，输出这个字符串的所有全排列。 我们假设对于小写字母有'a' < 'b' < ... < 'y' < 'z'，而且给定的字符串中的字母已经按照从小到大的顺序排列。

输入描述:

输入只有一行，是一个由不同的小写字母组成的字符串，已知字符串的长度在1到6之间。

输出描述:

输出这个字符串的所有排列方式，每行一个排列。要求字母序比较小的排列在前面。

输入

abc

输出

abc
acb
bac
bca
cab
cba

使用STL标准库函数

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    string str;
    while(getline(cin,str))
    {
        sort(str.begin(),str.end());
        do{
            cout << str << endl;
        }while(next_permutation(str.begin(), str.end()));
        cout << endl;
    }
    return 0;
}

使用递归

//算法思想：全排列的n皇后问题思路，对问题进行递归实现。
#include <iostream>
#include <string.h>
#include <algorithm>
#define max 7
using namespace std;

//P为当前排列，hashTable记录x是否已经在p中
int n;                            //n为字符串长度，当前处理排列的index位
int hashTable[max] = {0};
char p[max];                     //储存全排列结果的数组

void generateP(int index,char str[])
{
    if(index == n)                     //递归边界
    {
        for(int i=0;i<n;++i)
        {
            cout << p[i];              //输出当前排列
        }
        cout << endl;
        return;
    }
    for(int x=0;x<n;++x)
    {
        if(hashTable[x] == 0)             //如果x不在p[0]~p[index-1]中
        {
            p[index] = str[x];            //令p的index位为先，即把str[x]加入当前排列
            hashTable[x] = 1;             //记x已经在p中

            generateP(index+1,str);       //处理排列的index+1位,index会从 0 增加到 n

            hashTable[x] = 0;             //已处理完p[index]为x的子问题，还原状态
        }
    }
}

int main(int argc, char const *argv[])
{
    char str[max];
    while(cin >> str)
    {
        n = strlen(str);
        sort(str,str+n);        
        generateP(0,str);
        cout << endl;
    }
    return 0;
}