问题描述：http://acm.hdu.edu.cn/showproblem.php?pid=1716
简单的讲：
Sample Input1 2 3 4
1 1 2 3
0 1 2 3
0 0 0 0
Sample Output
1234 1243 1324 1342 1423 1432
2134 2143 2314 2341 2413 2431
3124 3142 3214 3241 3412 3421
4123 4132 4213 4231 4312 4321
1123 1132 1213 1231 1312 1321
2113 2131 2311
3112 3121 3211
1023 1032 1203 1230 1302 1320
2013 2031 2103 2130 2301 2310
3012 3021 3102 3120 3201 3210
这是一道典型的全排列问题。可以用STL的next_permutation()函数，标准库全排列next_permutation()的返回值:bool类型
分析next_permutation函数执行过程:
假设数列 d1,d2,d3,d4……
范围由[first,last)标记，调用next_permutation使数列逐次增大，这个递增过程按照字典序。例如，在字母表中，abcd的下一单词排列为abdc，但是，有一关键点，如何确定这个下一排列为字典序中的next，而不是next->next->next……
若当前调用排列到达最大字典序，比如dcba，就返回false，同时重新设置该排列为最小字典序。
返回为true表示生成下一排列成功。下面着重分析此过程：
根据标记从后往前比较相邻两数据，若前者小于（默认为小于）后者，标志前者为X1（位置PX）表示将被替换，再次重后往前搜索第一个不小于X1的数据，标记为X2。交换X1，X2，然后把[PX+1，last)标记范围置逆。完成。
要点：为什么这样就可以保证得到的为最小递增。
从位置first开始原数列与新数列不同的数据位置是PX，并且新数据为X2。[PX+1，last)总是递减的，[first,PX)没有改变，因为X2>X1,所以不管X2后面怎样排列都比原数列大，反转[PX+1，last）使此子数列(递增)为最小。从而保证的新数列为原数列的字典序排列next。
明白了这个原理后，看下面例子：
int main(){
int a[] = {3,1,2};
do{
}
while (next_permutation(a,a+3));
return 0;
}
输出：312/321
所以要想得到所有全排列
int a[] = {3,1,2};
另外，库中另一函数prev_permutation与next_permutation相反，由原排列得到字典序中上一次最近排列。所以
int main(){
int a[] = {3,2,1};
do{
}
while (prev_permutation(a,a+3));
return 0;
}
才能得到123的所有排列。
//方法1：用STL的next_permutation()函数
#include "stdafx.h"
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int Num[4],pre,i;
bool firstCase=true;
while(cin>>Num[0]>>Num[1]>>Num[2]>>Num[3])
{
if(Num[0]==0 && Num[1]==0 && Num[2]==0 && Num[3]==0)break;
if(!firstCase) cout<<endl;
firstCase = false;
sort(Num,Num+4);
i=0;
while(Num[i]==0) ++i;
pre = Num[i];//第一个非0数字
while(true)
{
if(Num[0]!=0)
{
if(Num[0]!=pre)
{cout<<"\n";pre=Num[0];}
cout<<Num[0]<<Num[1]<<Num[2]<<Num[3];
if(next_permutation(Num,Num+4))
{
if(Num[0]==pre)
cout<<" ";
}
else
{cout<<endl;break;}
}
else if(!next_permutation(Num,Num+4))
{cout<<endl;break;}
}
}
return 0;
}
第二种方法：
字典序法：对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后。
[例]字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是:123,132,213,231,312,321。
[注意] 一个全排列可看做一个字符串，字符串可有前缀、后缀。
1）生成给定全排列的下一个排列 所谓一个的下一个就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。
[例]839647521是1–9的排列。1—9的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到了987654321，也就没有下一个了。否则找出第一次出现下降的位置。
算法思想：
设P是[1,n]的一个全排列。
P=P1P2…Pn=P1P2…Pj-1PjPj+1…Pk-1PkPk+1…Pn , j=max{i|PiPj} ,对换Pj，Pk，将Pj+1…Pk-1PjPk+1…Pn翻转， P’= P1P2…Pj-1PkPn…Pk+1PjPk-1…Pj+1即P的下一个
例子:839647521的下一个排列.
从最右开始,找到第一个比右边小的数字4(因为4<7，而7>5>2>1),再从最右开始,找到4右边比4大的数字5(因为4>2>1而4<5),交换4、5,此时5右边为7421,倒置为1247,即得下一个排列:839651247.
1、从数列的右边往左边寻找第一个非递增的数，记为p[m],本例中p[m]=4，下标m从0开始；
for（int i=len-1;i>=1;i--）
{
if(p[i]<p[i-1]) break;
}
或
for（int i=len-2;i>=0;i--）
{
if(p[i]<p[i+1]) break;
}
2、从数列的右边往左边寻找第一个大于p[m]的数p[n],本例中p[n]=5;
for（int j=len-1;j>i;j--）
{
if(p[j]>p[i]) break;
}
3、交换p[m]与p[n]，本例交换之后为：839647521——>839657421
4、将i+1之后位置上的所有数字倒置。本例为7421——>1247
5、将数列的前缀添加上，即得下一个排列:839651247.
#include "stdafx.h"
#include <iostream>
#include <algorithm>
using namespace std;
int str[4];
int sh;
void temp(int i,int j)
{
int temp=str[i];
str[i++]=str[j];
str[j]=temp;
}
void fun(int len)
{
int i,j,k,flag=1;
while(1){
if(str[0]!=0)
{
if(sh!=str[0]&&sh!=0){cout<<endl;flag=1;}
if(!flag)cout<<" ";
flag=0;
cout<<str[0]<<str[1]<<str[2]<<str[3];
sh=str[0];
}
for(i=len-2;i>=0;i--)
{
if(str[i]<str[i+1])
break;
}
if(i<0)return;
for(j=len-1;j>i;j--)
if(str[j]>str[i])
break;
temp(i,j);
i++;
for(k=0;len-1-i>2*k;k++)
{
temp(i+k,len-1-k);
}
}
}
int main()
{
bool flag=false;
while(cin>>str[0]>>str[1]>>str[2]>>str[3]&&(str[0]||str[1]||str[2]||str[3]))
{
if(flag)cout<<endl;
flag=true;
sort(str,str+4);
sh=str[0];
fun(4);
cout<<endl;
}
}