Question

非递归的全排列，谢谢！！！ 列入 abc C写 abc acb bac bca cab cba

全排列Time Limit: 1 Sec Memory
Limit: 65 MB
Submit: 16 Solved: 2
[Submit][Status][Edit]
Description

给定一个由不同的小写字母组成的字符串，输出这个字符串的所有全排列。

我们假设对于小写字母有'a' < 'b' < ...
< 'y' < 'z'。

Input

输出只有一行，是一个由不同的小写字母组成的字符串，已知字符串的长度在1到6之间。

Output

输出这个字符串的所有排列方式，每行一个排列。要求字母序比较小的排列在前面。字母序如下定义：

已知S =
s1s2...sk , T =
t1t2...tk，则S < T 等价于，存在p (1 <= p <=
k)，使得
s1 = t1, s2 = t2, ...,
sp - 1 = tp - 1, sp <
tp成立。

Sample Input

abc

Sample Output

abc
acb
bac
bca
cab
cba

若以下回答无法解决问题，邀请你更新回答

Answer 1

/************************************************************************
首先先将最后一个数从右往左依次交换输出，然后判断个数是否为基数，交换离该数最远端的两个数，
再把第一个数从左往右交换输出，交换远端的两个数，如此进行循环就能排列完全部的数。
这说得可能比较抽象，看一个例子：

　　E.g： 　　　1 2 3 4

第一次：（从右往左）：1 2 4 3 --- 1 2 4 3 --- 1 4 2 3 --- 4 1 2 3 把最后一个数依次往前移

　　　　　　　　　　　交换：2 和 3 ---> 4 1 3 2

第二次：（从左往右）：4 1 3 2 --- 1 4 3 2 --- 1 3 4 2 --- 1 3 2 4 把第一个数依次往后移

　　　　　　　　　　　交换：1 和 3 ----> 3 1 2 4 重复第一次，知道把所有数输出为止
/************************************************************************/
#include <iostream.h>
#include <iomanip>
int n;
void swap(int *a,int *b); //交换函数
void print(int a[]); //打印交换后的每一组数
int jfc(); //求阶乘函数
int jmp(int n); //跳转函数
void sort(int a[]); //全排列函数

int main(){
while(cin>>n)
{
while(n<=0)
{
cout<<"输入有误！请重新输入: ";
cin>>n;
}
int *a=new int[n];
for(int i=0;i<n;i++)
a[i]=i+1;
sort(a);
delete []a;
}
system("pause");
return 0;
}

void swap(int *a,int *b)
{
int t=*a;
*a=*b;
*b=t;
}
void print(int a[])
{
for(int i=0;i<n;i++)
cout<<char(a[i]-1+'a')<<' ';
cout<<endl;
}
int jfc()
{
int s=1;
for(int i=1;i<=n;i++)
s*=i;
return s;
}
int jmp(int n)
{
if(n>jfc())
return 0;
}
void sort(int a[])
{
int m=1,count=0; //m统计全排列的个数,count统计行数
int *p1,*p2;
for(p1=a+n-1,p2=a+n-2;p1>=a+1,p2>=a;p1--,p2--)
{
print(a);
swap(p1,p2);
m++;
}
count++;
while(m<=jfc()){
if(count%2)
{ print(a);
swap(&a[n-1],&a[n-2]);
m++;
if(!jmp(m))
break;
for(p1=a,p2=a+1;p1<=a+n-2,p2<=a+n-1;p1++,p2++)
{
print(a);
swap(p1,p2);
m++;
}
count++;
}
else
{
print(a);
swap(&a[0],&a[1]);
m++;
if(!jmp(m))
break;
for(p1=a+n-1,p2=a+n-2;p1>=a+1,p2>=a;p1--,p2--)
{
print(a);
swap(p1,p2);
m++;
}
count++;
}
}
cout<<"共有"<<m-1<<"种排列"<<endl;
}