生成字符串全排列
程序员文章站
2022-06-28 12:46:45
...
题目描述:
对于一个包含字母,数字,符号的字符串,要求打印出它的全排列和排列总数。每个结果占一行。
解题思路:
先对字符串按照ACSII码排序,然后利用循环嵌套递归的方式,得到所有的结果。
EXAMPLE:
a | b | c |
a | c | d |
b | a | c |
b | c | a |
c | a | b |
c | b | a |
我们注意到,首先对abc的末尾的bc进行变换,得到abc和acb;
然后,再按字典序对第一位进行变换,并且第二位和第三位按照字典序排列,得到bac和bca;
最后重复第二步,得到cab和cba;
AC代码:
#include <iostream>
#include <string>
#include<cstdio>
#include<algorithm>
using namespace std;
string s;
long long cnt = 0;//记录排列的总数,虽然可以利用公式直接计算,但是设置全局变量会使代码更加简洁
void print_permutation(int n, int* P, int* A, int cur) {
if (cur == n) {
cnt++;
for (int k = 0; k < n; k++) {
printf("%c", (char)A[k]);//将原本是ASCII码的数字转换成对应的字符
}
printf("\n");
}
else {
for (int i = 0; i < n; i++) {
bool flag=1; //标记
for (int j = 0; j < cur; j++) {
if (A[j] == P[i]) {
flag=0;
}
}
if (flag) {
A[cur] = P[i];
print_permutation(n, P, A, cur + 1);
}
}
}
}
int main() {
int A[100000], P[100000];
int i, n;
getline(cin, s);
n = s.length();
s.c_str();
for (int k = 0; k < n; k++) {
P[k] = s[k] + '\0'; //将字符串里的字符转换成它对应的ASCII码
}
sort(P, P + n); //将需要被排列的字符数组按照字典序排序
print_permutation(n, P, A, 0);
cout << cnt << endl;
return 0;
}
关于递归函数print_permutation(int n, int* P, int* A, int cur)
这个函数是利用cur(即current)来维护的,即
函数执行过程:(注意观察cur和i)
cur=0,i=0->flag=1->A[0]=P[0]=a->cur=1->i=0->j=0->flag=0->i=1->j=0->A[0]!=(P[1]=b)->A[1]=P[1]->cur=2->i=0->A[0]==P[0]->flag=0->i=1->A[0]!=P[1]->A[1]==P[1]->i=2->A[0]!=P[2]&&A[1]!=P[2]->A[2]=P[2]->cur=3->print->cur=1->i=2->A[0]!=P[2]->A[1]=P[2]->cur=2->i=0->A[0]==P[0]->i=1->A[0]!=P[1]&&A[1]!=P[1]->A[2]=P[1]->cur=0,i=1->……完成了生成abc和acb的排列。
粉红色 | 第一层递归 |
橙色 | 第二层递归 |
绿色 | 第三层递归 |
紫色 | 第四层递归 |