使用C语言解决字符串全排列问题
|
问题 思路
基本解决方法
#include <iostream>
#include <string>
using namespace std;
void permute1(string prefix,string str)
{
if(str.length() == 0)
cout << prefix << endl;
else
{
for(int i = 0; i < str.length(); i++)
permute1(prefix+str[i],str.substr(0,i)+str.substr(i+1,str.length()));
}
}
void permute1(string s)
{
permute1("",s);
}
int main()
{
//method1,unable to remove duplicate permutations.
cout << "method1" << endl;
permute1("ABA");
}
优点：该方法易于理解，但无法移除重复的排列，如：s="ABA"，会生成两个“AAB”。 方法2：利用交换的思想，具体见实例，但该方法不如方法1容易理解。
#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
void swap(char* x,char* y)
{
char tmp;
tmp = *x;
*x = *y;
*y = tmp;
}
/* Function to print permutations of string
This function takes three parameters:
1. String
2. Starting index of the string
3. Ending index of the string. */
void permute(char *a,int i,int n)
{
int j;
if (i == n)
printf("%sn",a);
else
{
for (j = i; j <= n; j++)
{
if(a[i] == a[j] && j != i) //为避免生成重复排列，当不同位置的字符相同时不再交换
continue;
swap((a+i),(a+j));
permute(a,i+1,n);
swap((a+i),(a+j)); //backtrack
}
}
}
int main()
{
//method2
cout << "method2" << endl;
char a[] = "ABA";
permute(a,2);
return 0;
}
两种方法的生成结果： method1 ABA AAB BAA BAA AAB ABA method2 ABA AAB BAA 下面来看ACM题目实例 示例题目 题目描述： ac代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct seq
{
char str[7];
};
struct seq seqs[721];
int count;
void swap(char *str,int a,int b)
{
char temp;
temp = str[a];
str[a] = str[b];
str[b] = temp;
}
void permutation_process(char *name,int begin,int end) {
int k;
if (begin == end - 1) {
strcpy(seqs[count].str,name);
count ++;
}else {
for (k = begin; k < end; k ++) {
swap(name,k,begin);
permutation_process(name,begin + 1,end);
swap(name,begin);
}
}
}
int compare(const void *p,const void *q)
{
const char *a = p;
const char *b = q;
return strcmp(a,b);
}
int main()
{
char name[7];
int i,len;
while (scanf("%s",name) != EOF) {
count = 0;
len = strlen(name);
permutation_process(name,len);
qsort(seqs,count,sizeof(seqs[0]),compare);
for (i = 0; i < count; i ++) {
printf("%sn",seqs[i].str);
}
printf("n");
}
return 0;
}
去掉重复的全排列
由于全排列就是从第一个数字起，每个数分别与它后面的数字交换，我们先尝试加个这样的判断――如果一个数与后面的数字相同那么这两个数就不交换了。例如abb，第一个数与后面两个数交换得bab，bba。然后abb中第二个数和第三个数相同，就不用交换了。但是对bab，第二个数和第三个数不同，则需要交换，得到bba。由于这里的bba和开始第一个数与第三个数交换的结果相同了，因此这个方法不行。 换种思维，对abb，第一个数a与第二个数b交换得到bab，然后考虑第一个数与第三个数交换，此时由于第三个数等于第二个数，所以第一个数就不再用与第三个数交换了。再考虑bab，它的第二个数与第三个数交换可以解决bba。此时全排列生成完毕！ 这样，我们得到在全排列中去掉重复的规则： 贴出上面ac代码的去重版本：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct seq
{
char str[7];
};
struct seq seqs[721];
int count;
int is_swap(char *str,int k)
{
int i,flag;
for (i = begin,flag = 1; i < k; i ++) {
if (str[i] == str[k]) {
flag = 0;
break;
}
}
return flag;
}
void swap(char *str,int b)
{
char temp;
temp = str[a];
str[a] = str[b];
str[b] = temp;
}
void permutation_process(char *name,int end) {
int k;
if (begin == end - 1) {
strcpy(seqs[count].str,name);
count ++;
}else {
for (k = begin; k < end; k ++) {
if (is_swap(name,begin,k)) {
swap(name,begin);
permutation_process(name,end);
swap(name,begin);
}
}
}
}
int compare(const void *p,b);
}
int main()
{
char name[7];
int i,len;
while (scanf("%s",compare);
for (i = 0; i < count; i ++) {
printf("%sn",seqs[i].str);
}
printf("n");
}
return 0;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
