承接上文，這次以遞推的思維，介紹組合學當中一個很經典的問題。

這個問題最開始由瑞士數學家歐拉提出，原始的問題被叫做“裝信封問題”，問題的大意就是:有n封信和n封它們各自對應的信封，如果郵遞員想要把每封信都放在不屬于這封信的信封，那么請問有多少種排法。（這郵遞員真無聊）
想必這個問題在中學階段數學的【排列組合】都有過接觸，但是我記憶非常深刻的是，老師講到這個模型，自己找了一下n = 5的情況就停止了，然后讓大家把前面的數字序列背下來。今日故地重游不禁覺得老師教的好坑爹，搞學習還是要親歷親為自主探究。
雖然這個問題的排列數有一個很長的通式，但是想用計算機編程實現，必須要把它簡化成可以一步一步執行的遞推式。

假設b被放到了A當中。

情況1：a在B中。

這種情況下，剩下的（n-2）個球的排列就已經和a、b、A、B沒有關系，這種情況的排列數也就是n-2時候的【全錯位排列數】

情況2：a不在B中。

這種情況下，就要完成a,c,d,e……與B,C,D,E......的錯位排列。而基于a不在B中的條件，可以把a和B看成【對應】信封，這樣就相當于是n-1封信進行【全錯位排列】。

以上是b在A中的全錯排列數，即f(n-1)+f(n-2)。而b可以放在剩除了B以外的任何一個信封當中，因此得到“裝信封問題”中，n封信的全錯位排列數的遞推式是： f(n) = (n-1)*[f(n-1) + f(n-2)](n > 2)

有了【全錯位排列】這個模型，就可以很輕松的解決以下問題了。(Problem source : hdu 2048)

Problem Description
HDU 2006'10 ACM contest的頒獎晚會隆重開始了！ 為了活躍氣氛，組織者舉行了一個別開生面、獎品豐厚的抽獎活動，這個活動的具體要求是這樣的：
首先，所有參加晚會的人員都將一張寫有自己名字的字條放入抽獎箱中； 然后，待所有字條加入完畢，每人從箱中取一個字條； 最后，如果取得的字條上寫的就是自己的名字，那么“恭喜你，中獎了！”
大家可以想象一下當時的氣氛之熱烈，畢竟中獎者的獎品是大家夢寐以求的Twins簽名照呀！不過，正如所有試圖設計的喜劇往往以悲劇結尾，這次抽獎活動最后竟然沒有一個人中獎！
我的神、上帝以及老天爺呀，怎么會這樣呢？
不過，先不要激動，現在問題來了，你能計算一下發生這種情況的概率嗎？
不會算？難道你也想以悲劇結尾？！

讀題可以看到，題目需要輸出概率，分子顯然是【全錯位排列數】，而分母是所有可能情況，即是n的階乘。

再看這個題.(Problem source : 2049)

Problem Description
國慶期間,省城HZ剛剛舉行了一場盛大的集體婚禮,為了使婚禮進行的豐富一些,司儀臨時想出了有一個有意思的節目,叫做"考新郎",具體的操作是這樣的:
首先,給每位新娘打扮得幾乎一模一樣,并蓋上大大的紅蓋頭隨機坐成一排; 然后,讓各位新郎尋找自己的新娘.每人只準找一個,并且不允許多人找一個. 最后,揭開蓋頭,如果找錯了對象就要當眾跪搓衣板...
看來做新郎也不是容易的事情...
假設一共有N對新婚夫婦,其中有M個新郎找錯了新娘,求發生這種情況一共有多少種可能.

可以看到這兩個題目都是在全錯位排列的基礎上稍做了一些改動，這個題目需要我們輸出所有情況數目。 顯然為了完成這件事，先要找出那M個找錯的悲催新郎，得到一個組合數，然后再乘以（這里涉及【組合學】里一個簡單的分步乘法原理）那M個人的【全錯排列數】即可得到答案。而至于得到那個組合數，設計兩個循環分別得到分子和分母再相除即可。

再看一個應用稍微靈活的有關錯排的題目。 (Problem source : hdu 2068)

Problem Description
今年暑假杭電ACM集訓隊第一次組成女生隊,其中有一隊叫RPG,但做為集訓隊成員之一的野駱駝竟然不知道RPG三個人具體是誰誰。RPG給他機會讓他猜猜，第一次猜：R是公主，P是草兒，G是月野兔；第二次猜：R是草兒，P是月野兔，G是公主；第三次猜：R是草兒，P是公主，G是月野兔；......可憐的野駱駝第六次終于把RPG分清楚了。由于RPG的帶動，做ACM的女生越來越多，我們的野駱駝想都知道她們，可現在有N多人，他要猜的次數可就多了，為了不為難野駱駝，女生們只要求他答對一半或以上就算過關，請問有多少組答案能使他順利過關。

數理分析：這道題乍一看好像和錯排沒什么關系，因為題目中提到只要答對一半或以上即可，好像和錯排沾不上邊。但是仔細分析一下會發現聯系。我們從答對一半(m，對于奇偶的分析是后話)，我們要從n個里面選出m，然后乘以剩下的n-m個元素的全錯排，就是答對m個的所有總數，然后m+1，依次計算，便可以得到最終的結果。

編程實現方面也是比較簡單，需要打一個錯排的表然后再寫有個計算組合數的函數，這里寫計算組合數的函數有一個技巧是變量都要用double，否則會出現精度上的錯誤。另外值得注意的一點是，這里最多有25個元素，錯排最多也就是12個元素，所以打錯排的表的時候，數組不必開太大。

代碼如下。

#include<stdio.h>
double a[15];

double Con(int m , int n)
{

   double ret = 1 , i;
   for(i = 0;i < m;i++)
          ret *= (n - i)/(m - i);
   return ret;
}
void make_list()
 {
     int i;
     a[1] = 0;
     a[2] = 1;
       for(i = 3;i <= 15;i++)
           {
             a[i] = (i - 1)*(a[i - 1] + a[i - 2]);
             //printf("%.0lf
",a[i]);
           }
 }

 int main()
 {
        double ans;
       int n , m ,i;
       make_list();
    while(~scanf("%d",&n) , n)
        {
             ans = 0;

             if(n%2 == 0)
                  m = n / 2;
             else
                  m = n / 2 + 1;

            for(i = m;i < n;i++)
                 ans += Con(i , n)*a[n - i];

                printf("%.0lf
",ans + 1);

        }

 }

再看一道用到全錯位排列公式的簡單題目。(Problem source : 1465)

Problem Description
大家常常感慨，要做好一件事情真的不容易，確實，失敗比成功容易多了！ 做好“一件”事情尚且不易，若想永遠成功而總從不失敗，那更是難上加難了，就像花錢總是比掙錢容易的道理一樣。 話雖這樣說，我還是要告訴大家，要想失敗到一定程度也是不容易的。比如，我高中的時候，就有一個神奇的女生，在英語考試的時候，竟然把40個單項選擇題全部做錯了！大家都學過概率論，應該知道出現這種情況的概率，所以至今我都覺得這是一件神奇的事情。如果套用一句經典的評語，我們可以這樣總結：一個人做錯一道選擇題并不難，難的是全部做錯，一個不對。
不幸的是，這種小概率事件又發生了，而且就在我們身邊： 事情是這樣的——HDU有個網名叫做8006的男性同學，結交網友無數，最近該同學玩起了浪漫，同時給n個網友每人寫了一封信，這都沒什么，要命的是，他竟然把所有的信都裝錯了信封！注意了，是全部裝錯喲！
現在的問題是：請大家幫可憐的8006同學計算一下，一共有多少種可能的錯誤方式呢？

這是一道很標準很基礎的錯排題目，只是在編寫的時候，對于數據類型——到底用__int64還是double，好像對于不同的題目有不同的限制，不過這是oj的問題了。

簡單的代碼如下。

#include<stdio.h>
__int64 a[25];
void make_list()
{
   a[1] = 0 , a[2] = 1;
     int i;
      for(i = 3;i <= 20;i++)
         a[i] = (i - 1)*(a[i - 2] + a[i - 1]);
}

int main()
{
  int n;
  make_list();
  while(scanf("%d",&n) != EOF)
     printf("%I64d
",a[n]);
}

再來看一道有關錯排的簡單題目。(Problem source : hdu 4534)

Problem Description
　　吉哥還是那個吉哥 　　那個江湖人稱“嘰嘰哥”的基哥 　　 　　每當節日來臨，女友眾多的嘰嘰哥總是能從全國各地的女友那里收到各種禮物。 　　有禮物收到當然值得高興，但回禮確是件麻煩的事！ 　　無論多麻煩，總不好意思收禮而不回禮，那也不是嘰嘰哥的風格。 　　 　　現在，即愛面子又摳門的嘰嘰哥想出了一個絕妙的好辦法：他準備將各個女友送來的禮物合理分配，再回送不同女友，這樣就不用再花錢買禮物了！ 　　 　　假設嘰嘰哥的n個女友每人送他一個禮物（每個人送的禮物都不相同），現在他需要合理安排，再回送每個女友一份禮物，重點是，回送的禮物不能是這個女友之前送他的那個禮物，不然，嘰嘰哥可就攤上事了，攤上大事了...... 　　 　　現在，嘰嘰哥想知道總共有多少種滿足條件的回送禮物方案呢？

這道題目在錯排的基礎上，加入的求余處理。我們可以想象，根據錯排的遞推式，打表循環幾次就可以把__int64給打爆，因此這里題目要求進行求余處理。 在算法實現上，我們可以先求出f[i - 1] + f[i - 2]，然后求一步余，然后再乘以(i - 1)，再求余，這種分步求余的方式能夠進一步的防止數據的溢出。

代碼如下:

#include<stdio.h>
__int64 a[105];
const int MOD = 1000000007;
void make_list()
  {
     a[1] = 0;
     a[2] = 1;
     int i;
        for(i = 3;i <= 100;i++)
          {
            a[i] = a[i - 1] + a[i - 2];
             a[i] %= MOD;
             a[i] *= i - 1;
             a[i] %= MOD;
          }
  }

  int main()
  {
      make_list();
     int n , T;
     scanf("%d",&T);
     while(T--)
         {
            scanf("%d",&n);
            printf("%I64d
",a[n]);
         }
  }

總結

以上是生活随笔為你收集整理的《程序设计中的组合数学》——全错位排列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。