学步园

首先我们来说一下这个问题的基本算法，其实很简单，是一个典型的递归算法：

假设给定的字符串是 babc     （[]中的为下一次递归的输入）：

1.       abbc        排序： 让相等的字符连续

2.       a[bbc]     求解以第一个字符开头的组合

    |

3.       b[abc]     发现第二个字符b和上一组组合的头a 不相等，所以调换，并求解一新头（b）      开头的组合

4.       abbc          还原上一次的交换

     |

5.       abbc         b和第3步中的第一个字符b相等跳过（以b开头的组合已经在第3步中求解了）

        |

6.       c[bba]         c和上一组组合的头（b） 不相等，所以调换，并求解一新头（c)开头的组合

#include <iostream>
#include <algorithm>
using namespace std;


void SubPermutation(char a[], int start)
{
	if(start==strlen(a)-1)
	{
		for(int i=0; i<=strlen(a)-1; i++)
			cout<<a[i];
		cout<<endl;
	}
	else
	{
		char head=a[start];
		for(int i=start; i<=strlen(a)-1; i++)
		{
			if(i==start)
				SubPermutation(a, start+1);
			else
			{
				if(a[i]!=head)
				{
					swap(a[i], a[start]);
					head=a[start];
					SubPermutation(a, start+1);
					swap(a[i], a[start]);

				}
			}
		}
	}
}

void main()
{
	char s[]="babc";
	sort(s,s+strlen(s)-1);//先排序，让相等的字符连续
	SubPermutation(s, 0);

}

参见：http://blog.csdn.net/zfscsd/article/details/5281850