任意一个字符串的全排列算法(可以有重复的字符)

类别:VC语言 点击:0 评论:0 推荐:


////////////////////////////////////////////////////////
// 姓名:梁迅
// 学号:02d470
// 完成时间:10/8/2002
// 文件名:1.cpp
/////////////////////////////////////////////////////////

#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)
{
 int j;
 char temp;
 for(j = 0; j < n; j ++)
  if(s[j] == s[j - 1])
   ;
  else if(s[j] != '#')// 如果标志为不为'#',
  {
   d[i] = s[j];// 把源串的一个字符赋给目的串。
   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;
   }
}

 

本文地址:http://com.8s8s.com/it/it2240.htm