最近想对算法进行一些归纳，找了几个全排列的非递归程序，都是利用字符交换的技巧实现的，不太好理解，我编写了利用栈实现人对每个位置进行穷举，并在到顶后逐步回退的程序。

例如，abc三个字符，按本程序/人的穷举过程，打印的排列次序有：

abc

acb

bac

bca

cab

cba

#include <iostream>
using namespace std;

typedef struct Stack{
	int top;
	int elem[100];
}Stack;
void initStack(Stack &S){
	S.top=0;
}
void Push(Stack &S, int e){
	S.elem[S.top]=e;
	S.top++;
}
int Pop(Stack& S){
	int e=-11111;
	if(S.top>0)
	{
		S.top--;
		e=S.elem[S.top];
	}
	return e;	
}
int IsExist(Stack S, int e){
	int i;
	for(i=0;i<S.top;i++)
		if(S.elem[i]==e)
			return	1;
	return 0;
}
int EmptyStack(Stack S){
	return S.top==0?1:0;
}
void PrintStack(Stack S, char str[]){
	int i;
	for(i=0;i<S.top;i++)
		cout<<str[S.elem[i]];
	cout<<endl;
}
int getNextIndex(int e, int n, Stack S){
	while(IsExist(S,e) && e<n)
		e++;
	return e;		
} 
void Pushs(Stack& S, int n)//对于从S.top位置开始的后续所有位置，都压入初始的符号位置。 
{
	int e;
	while(S.top<n)
	{
		e=getNextIndex(0, S.top, S);
		Push(S, e);		
	}		
}
void Permutation(char str[], int n){
	Stack S;
	int i;
	int e;
	int count=0;
	initStack(S);
	for(i=0;i<n;i++)
		Push(S, i);
	PrintStack(S, str);
	count++;
	
	//算法：初始压栈满0 1 2 3 4 ...n-1； 代表第一个初始的全排列。 
	//每次先出栈；如果当前位置未到底n-1，那么+1后压栈，如果到底的话持续回退；----该步寻找最近的需要往前探索的点； 
	//如果栈空，代表全部都探索完了；
	//如果栈不空，对于当前位置，获取下一个探索位置；然后后续全部压入对应位置的第一个不重复字符的索引；然后打印。 
	while(1){			
		e=Pop(S);
		while(getNextIndex(e+1, n, S)==n && !EmptyStack(S))
			e=Pop(S);//从后往前找到第一个需要继续探测的位置；
			 
		if(EmptyStack(S) && e==n-1)
			break;
		else
		{	
			e=getNextIndex(e+1, n, S);
			Push(S, e);
			Pushs(S, n);
			PrintStack(S, str);	
			count++;		
		}
			
	}	
	cout<<n<<"个字符的排列总数为："<<count<<endl;
}
 
int main()
{
	
	char str[]="abcdefg";
	int n=6;	
	Permutation(str, n);    
    return 0;
}