生成字符串的全排列

客官°小女子只卖身不卖艺 2022-05-23 22:11 186阅读 0赞

问题：

生成字符串的全排列，例如：abc

abc,bca,cba,bac,acb,cab

要考虑有重复元素的情况如：aab

aab,baa, aba

思路：

这是一个组合问题，使用回溯法在解空间中遍历。

注意两个问题：

1，每一轮递归决定排列中的一位，该位可取字符串中所有字符的种类；

2，对于深度不为1的递归，可选择的一定不能是之前选过的了，

所以之前访问过的结点应该做好标记。

代码：

#include "stdafx.h"
    #define N 21
    #include <stdio.h>
    #include <string.h>
    // 声明。
    char d[N];
    void Permutation(char s[], int i, int l);
    void Sort(char s[]);
    int   count = 0;
    void main()
    {
    	char s[N];
    	// 输入源字符串
    	printf("请输入一个不超过20个字符的字符串：");
    	gets(s);
    	// 排序，排列并输出
    	Sort(s); 
    	Permutation(s, 0, strlen(s));
    }
    // 运用递归输出各种排列
    void Permutation(char s[], int i, int n)
    {
    	for(int j = 0; j < n; j ++)
    		if((j==0||s[j]!=s[j-1]) && s[j]!='#')// 不能选重复的，且该位的字符未被使用过
    		{
    			d[i] = s[j];						// 使用它
    			char temp = s[j];					// 保存
    			s[j] = '#';							// 标记为已使用
    			if(i == n - 1)						// 递归结束，找到了排列的最后一位
    			{
    				d[n] = '\0';					// 加结束标记
    				printf("%d:", ++ count);        // 打印出其结果
    				puts(d);
    			}
    			else 
    				Permutation(s, i + 1, n);// 递归调用
    			s[j] = temp;// 回溯
    		}
    }
    
    // 排序
    void Sort(char s[])
    {
    	int n = strlen(s);
    	int i, j;
    	char temp;
    	for(i = 0; i < n - 1; i ++)
    		for(j = i + 1; j < n; j ++)
    			if(s[i] > s[j])
    			{
    				temp = s[i];
    				s[i] = s[j];
    				s[j] = temp;
    			}
    }