欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

生成字符串全排列

程序员文章站 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进行变换,得到abcacb;

        然后,再按字典序对第一位进行变换,并且第二位和第三位按照字典序排列,得到bacbca;

        最后重复第二步,得到cabcba;

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的排列。

递归层数解释
粉红色 第一层递归
橙色 第二层递归
绿色 第三层递归
紫色 第四层递归

 

 

 

相关标签: COJ 排列组合