原创 不同字符串的全排列

不同字符串的全排列

方法一：
#include<stdio.h>
#include<string.h>
char b[100];
long aa=0;
int bb;
char *sub(char *q,int i)
{char g[100],*s;
int m;
for(m=0;m<i;m++)
{ g[m]=q[m];
}
while(g[i-1]!='\0')
{ g=q[i+1];
  i++;
}
s=g;
return s;
}
void sout(char *p,int j)
{ char *f,e[50]="0000000000000000000000000000",d[100];
  int k,i=0;
while(d[i-1]!='\0')
{d=p;
i++;
}
if(j==1)
{b[bb-1]=d[0];
//puts(b);
aa++;
}
else
{for(k=0;k<j;k++)
{ b[bb-j]=d[k];
f=sub(d,k);
i=0;
while(e!='\0')
{ e=f;
    i++;
}
sout(e,j-1);
}
}
}
void main()
{
  char a[]="ABCDEFGHIJkL";
  bb=strlen(a);
    sout(a,bb);
    printf("%ld\n%d\n",aa,bb);
}
不输出字符串b的情况下：
输入：ABCDEFGHIJ     
输出：3628800，10 
运行时间:4s左右
输入：ABCDEFGHIJK
输出：39916800，11
运行时间：35s左右（是4s的11倍左右）
输入：ABCDEFGHIJKL
输出：479001600，12
运行时间：6分17秒左右(我还以为是死循环！！) （是35s的12倍左右）
方法二:
#include<stdio.h>
char a[10]="ABCDEFGHI",b[10];
long n=0;
int i,s;
void sout(char *p,int j)
{ int k;
  int q=0;
if(j==0)
{ for(i=0;i<9;i++)
  for(s=i+1;s<9;s++)
      if(b==b)
          q++;

if(q==0)
{
//puts(b);
n++;
}
}else
{for(k=0;k<9;k++)
 {b[9-j]=p[k];
  sout(a,j-1);
 }
}
}
void main()
{ sout(a,9);
  printf("%ld",n);
}
不输出字符串b的情况下：
输入：ABCDEFGH    
输出：40320
运行时间:6s左右
输入：ABCDEFGHI
输出：362880
运行时间：3分钟左右
两方法比较：
方法二空间复杂度比方法一小
但时间复杂度比方法一大

总结：程序不是随便设计，真的要讲究方法。大数目是检验程序好坏的好方法
看来还要再优化上面的程序！！

方法三（网上找的）

#include <stdio.h>
#include<string.h>
/*最多50无素*/
#define MAX    50
char dst[MAX] = {'\0'};
long n=0;
/*
[函数说明]
 递归调用,输出array的全排列.
[参数]
 char *pArray : 需要排列的array
 int  iIndex  : 当前排列编号
 int  iMax    : array元素个数.
[返回值]
 无.
[备注]
 iMax <= 数组大小.
 0 <= iIndex && iIndex <= iMax
*/
void combination(char *pArray, int iIndex, int iMax){
 int i;
 char cTemp;
 for(i = 0; i < iMax; i++){
  if(pArray == pArray[i-1]){
   ;
  }else if(pArray != '*'){
   dst[iIndex] = pArray;
   cTemp = pArray;
   pArray = '*';
   if(iIndex == iMax-1){
  n++;
   }else{
    //继续
    combination(pArray, iIndex+1, iMax);
   }
   //回溯
   pArray = cTemp;
  }
 }
}
void  main( )
{int m;
 char arr[]="ABCDEFGHIJKL";
m=strlen(arr);
 combination(arr, 0, m);
printf("%ld,%d",n,m);
}