C#算法之全排列遞歸算法實(shí)例講解

2020-01-24 02:19:49

字體：大中小

供稿：網(wǎng)友

排列：從n個(gè)元素中任取m個(gè)元素，并按照一定的順序進(jìn)行排列，稱為排列；

全排列：當(dāng)n==m時(shí)，稱為全排列；

比如：集合{ 1,2,3}的全排列為：

{ 1 2 3}
{ 1 3 2 }
{ 2 1 3 }
{ 2 3 1 }
{ 3 2 1 }
{ 3 1 2 }

我們可以將這個(gè)排列問題畫成圖形表示，即排列枚舉樹，比如下圖為{1,2,3}的排列枚舉樹，此樹和我們這里介紹的算法完全一致；

算法思路：

(1)n個(gè)元素的全排列=（n-1個(gè)元素的全排列）+（另一個(gè)元素作為前綴）；

(2)出口：如果只有一個(gè)元素的全排列，則說明已經(jīng)排完，則輸出數(shù)組；

(3)不斷將每個(gè)元素放作第一個(gè)元素，然后將這個(gè)元素作為前綴，并將其余元素繼續(xù)全排列，等到出口，出口出去后還需要還原數(shù)組；

這里先把集合中的元素理解為不會(huì)出現(xiàn)重復(fù)了，那么實(shí)現(xiàn)的方法（C++）如下：

復(fù)制代碼代碼如下:

成員管理，互評(píng)，文件共享，事務(wù)通知
#include <iostream>
using namespace std;

int sum = 0;//記錄有多少種組合

void Swap(char str[], int a, int b)
{
    char temp = str[a];
    str[a] = str[b];
    str[b] = temp;
}

void Perm(char str[], int begin, int end)
{
    if (begin == end)
    {
        for (int i = 0; i <= end; i++)
        {
            cout << str[i];
        }
        cout << endl;
        sum++;
        return;
    }
    else
    {
        for (int j = begin; j <= end; j++)
        {
            Swap(str, begin, j);
            Perm(str, begin + 1, end);
            Swap(str, j, begin);
        }
    }
}

int main()
{
    int n;
    char c[16];
    char tmp;

    cin >> n;
    tmp = getchar();    // 接受回車
    if (1 <= n && n <= 15) {
        for (int i = 0; i < n; i++) {
            c[i] = getchar();
        }
        Perm(c, 0, n - 1);
    }
    cout << sum;
    cout << endl;
    return 0;
}

實(shí)現(xiàn)后效果如下圖：

有重復(fù)元素的排列問題

然后現(xiàn)在的題目要求是排列中的元素是包含相同元素的，給定n以及待排的n個(gè)可能重復(fù)的元素。計(jì)算輸出n個(gè)元素的所有不同排列，因此上面那個(gè)算法顯然還是不夠好，因?yàn)橄嗤脑囟籍?dāng)成不同的元素，因此有了重復(fù)的排列在里面

去掉重復(fù)符號(hào)的全排列：在交換之前可以先判斷兩個(gè)符號(hào)是否相同，不相同才交換，這個(gè)時(shí)候需要一個(gè)判斷符號(hào)是否相同的函數(shù)。也就是下面的IsSwap（）；

對(duì)122，第一個(gè)數(shù)1與第二個(gè)數(shù)2交換得到212，然后考慮第一個(gè)數(shù)1與第三個(gè)數(shù)2交換，此時(shí)由于第三個(gè)數(shù)等于第二個(gè)數(shù)，所以第一個(gè)數(shù)不再與第三個(gè)數(shù)交換。再考慮212，它的第二個(gè)數(shù)與第三個(gè)數(shù)交換可以得到解決221。

去掉重復(fù)的規(guī)則：去重的全排列就是從第一個(gè)數(shù)字起每個(gè)數(shù)分別與它后面非重復(fù)出現(xiàn)的數(shù)字交換。

復(fù)制代碼代碼如下:

#include <iostream>
using namespace std;

int sum=0;//記錄有多少種組合

void Swap(char str[], int a, int b)
{
    char temp = str[a];
    str[a] = str[b];
    str[b] = temp;
}

bool IsSwap(char *pchar, int nBegin, int nEnd)
{
    for (int i = nBegin; i < nEnd; i++)
        if (pchar[i] == pchar[nEnd])
            return false;
    return true;
}

void Perm(char str[], int begin, int end)
{
    if (begin==end)
    {
        for (int i = 0; i <= end; i++)
        {
            cout << str[i];
        }
        cout << endl;
        sum++;
        return;
    }
    else
    {
        for (int j = begin; j <= end; j++)
        {
            if (IsSwap(str, begin, j))
            {
                Swap(str, begin, j);
                Perm(str, begin + 1, end);
                Swap(str, j, begin);
            }
        }
    }
}

int main()
{
    int n;
    char c[16];
    char tmp;

非遞歸的實(shí)現(xiàn)

實(shí)現(xiàn)思路：

要考慮全排列的非遞歸實(shí)現(xiàn)，先來考慮如何計(jì)算字符串的下一個(gè)排列。如"1234"的下一個(gè)排列就是"1243"。只要對(duì)字符串反復(fù)求出下一個(gè)排列，全排列的也就迎刃而解了。

如何計(jì)算字符串的下一個(gè)排列了？來考慮"926520"這個(gè)字符串，我們從后向前找第一雙相鄰的遞增數(shù)字，"20"、"52"都是非遞增的，"26 "即滿足要求，稱前一個(gè)數(shù)字2為替換數(shù)，替換數(shù)的下標(biāo)稱為替換點(diǎn)，再?gòu)暮竺嬲乙粋€(gè)比替換數(shù)大的最小數(shù)（這個(gè)數(shù)必然存在），0、2都不行，5可以，將5和2交換得到"956220"，然后再將替換點(diǎn)后的字符串"6220"顛倒即得到"950226"。

對(duì)于像"4321"這種已經(jīng)是最“大”的排列，采用STL中的處理方法，將字符串整個(gè)顛倒得到最“小”的排列"1234"并返回false。

復(fù)制代碼代碼如下:

//全排列的非遞歸實(shí)現(xiàn)
#include <iostream>
using namespace std;
void Swap(char *a, char *b)
{
    char t = *a;
    *a = *b;
    *b = t;
}
//反轉(zhuǎn)區(qū)間
void Reverse(char *a, char *b)
{
    while (a < b)
        Swap(a++, b--);
}
//下一個(gè)排列
bool Next_permutation(char a[])
{
    char *pEnd = a + strlen(a);
    if (a == pEnd)
        return false;
    char *p, *q, *pFind;
    pEnd--;
    p = pEnd;
    while (p != a)
    {
        q = p;
        --p;
        if (*p < *q) //找降序的相鄰2數(shù),前一個(gè)數(shù)即替換數(shù)
        {
            //從后向前找比替換點(diǎn)大的第一個(gè)數(shù)
            pFind = pEnd;
            while (*pFind <= *p)
                --pFind;
            //替換
            Swap(pFind, p);
            //替換點(diǎn)后的數(shù)全部反轉(zhuǎn)
            Reverse(q, pEnd);
            return true;
        }
    }
    Reverse(p, pEnd);//如果沒有下一個(gè)排列,全部反轉(zhuǎn)后返回true
    return false;
}
int QsortCmp(const void *pa, const void *pb)
{
    return *(char*)pa - *(char*)pb;
}
int main()
{
    int sum = 0;
    char szTextStr[16];
    cin >> szTextStr;
    char tmp = getchar();    // 接受回車

    //加上排序
    qsort(szTextStr, strlen(szTextStr), sizeof(szTextStr[0]), QsortCmp);
    int i = 1;
    cout << endl << endl << endl;
    do{
        cout<<szTextStr<<endl;
        sum++;
    } while (Next_permutation(szTextStr));

cout << sum<<endl;
return 0;
}