自己寫的遞歸，幾經(jīng)修改終于AC

判斷重復(fù)的語(yǔ)句很關(guān)鍵原來(lái)我的判斷是如果之前的值與現(xiàn)在的一樣且用過(guò)，則跳過(guò)，進(jìn)行下一次循環(huán)
但這樣會(huì)使之后的循環(huán)也跳過(guò)，導(dǎo)致不必要的查詢，從而導(dǎo)致了超時(shí)。。

優(yōu)化后是判斷之后的值是否與現(xiàn)在的一樣，如果沒(méi)用過(guò)就把之后的值賦值給輸出，這樣就沒(méi)問(wèn)題了

#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <stdlib.h>
using namespace std;

char input[200],output[200];
int used[200];
int group=0;
int cmp(const void* a,const void* b)
{
    return *(char*)a-*(char*)b;
}

void orderfun(int current,int length)   //current代表當(dāng)前打印第幾個(gè)
{
    for (int i=0;i<length;i++)
    {    
        if (i<length-1&&input[i]==input[i+1]&&used[i+1]==0)    //重復(fù)則運(yùn)行下一個(gè),判斷下一個(gè)是否用過(guò)很關(guān)鍵，若判斷上一個(gè)則超時(shí)了。。。會(huì)走很多彎路
             continue;
        if (used[i]==0)
        {
            
            output[current]=input[i];
            used[i]=1;
            if (current==length-1)      //打印一種排列
            {
                printf("%s\n",output);
            }
            else
                orderfun(current+1,length);
            used[i]=0;
        }
    }
}
int main()
{ 
    cin>>input;
    int len=strlen(input);
    qsort(input,len,sizeof(input[0]),cmp);
    memset(used,0,sizeof(used));
    orderfun(0,len);
}


這里還有一個(gè)用STL的方法做的很簡(jiǎn)單（STL類庫(kù)太強(qiáng)大了。。。）
#include <iostream>
#include <string>
#include <algorithm>
 
using namespace std;

int main()
{
    string str;
    while(cin>>str)
    {
        sort(&str[0],&str[0]+str.length());//先排序
        cout<<str<<endl;//輸出排序后的
        while(next_permutation(&str[0],&str[0]+str.length()))
        {
            cout<<str<<endl;
        }
    }
    return 0;
}

 

 下面有關(guān)next_permutation的介紹
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int a[10]={1,2,2,3,3,3,4,5,6,7};
    int cnt=0;
    do{
        cnt++;
    }while(next_permutation(a,a+10));    
    printf("%d\n",cnt);//輸出302400
    scanf("pause");
}

next_permutation的返回值如下：如果變換后序列是非減序的則返回0，否則返回1。
所以如果想用do{...}while(next_permutation(...));的方式生成一個(gè)集合的全排列，必須先做sort。
即 便做了sort，從上面的例子我們也可以看出，當(dāng)集合存在重復(fù)元素時(shí)，循環(huán)的次數(shù)并不是10!=3628800，302400是什么呢，恰是10!/ (2!*3!)，也就是這個(gè)多重集的全排列數(shù)。可見(jiàn)在處理有重復(fù)元素的"集合"時(shí)，它是正確的且高效的，只要記住一定要先sort