關于如何評價洗牌質量的猜想

?

洗牌算法是卡牌類游戲中必須使用的算法，本質上說洗牌算法的目的是使某個給定的順序更加的無序，因此出現了很多種洗牌算法。我們不重點討論如何洗牌，我們將眼光關注于洗出的牌是否達到我們預期的要求，以及如何衡量洗出的牌無序的程度。首先先看一個簡單有效的洗牌算法。

一、一個簡單的洗牌算法

一個比較容易實現的洗牌算法是這樣的，通過隨機選出兩張牌進行交換，通過多次這樣的重復操作，就能達到洗牌的目的。事實證明這種洗牌方式還是比較可行，最重要的是比較簡單，代碼如下。

//洗牌算法，隨機交換數組的兩個元素，交換數組長度次為一次洗牌
template<class?T>
void?mess(T?data[],unsigned?int?len)
{
????int?i=len,j,k;
????T?t;
????srand((unsigned?int)time(0));//隨機因子
????while(i--)//交換牌數次數
????{
????????while(true)//找出兩張不一樣的牌
????????{
????????????//隨機產生兩張牌
????????????j=rand()%len;
????????????k=rand()%len;
????????????if(j!=k)//不是同一個元素
????????????{
????????????????//交換
????????????????t=data[j];
????????????????data[j]=data[k];
????????????????data[k]=t;
????????????????//退出進行下一次交換
????????????????break;
????????????}
????????}
????}
}

這種算法通過對有序的（假設開始洗牌時是有序的，并以此為參考）N張牌進行N次隨機交換，事實達到了洗牌的目的。以下是一個20位有序牌幾次洗牌后的結果：

雖然得到了我們想要的洗牌效果，但是我們卻無法定量的衡量洗出牌的質量。換句話說就是如何確定洗出的牌究竟亂成什么樣子？為了驗證洗牌的質量，必須給出評價洗出的牌的一個定量的分析。?

二、如何評價洗出牌的質量

牌洗出什么樣子才算比較好，當然是越亂越好。但是這么說其實并不全面，在實際的卡牌游戲中，我們要達到的目的只需要保證下局游戲時洗出的牌要和洗牌之前的情形變化很大即可，這個就是洗牌算法的本身需要考慮的問題。假如給我們一副新的牌，內部是按照某個順序排列的，洗牌算法要達到的目的是盡量讓它混亂，但是混亂的結果如何呢？所以不論在任何情況下，計算出牌的混亂程度都是必須的，它可以為我們的進行其他流程提供參考。因此，歸根結底還是需要討論洗出牌的混亂程度。為了方便討論這個問題，我們有個基本假設：如果按照某個順序，無論是升序還是降序，這種順序的牌的混亂程度應該定義為0。很明顯，有序的牌是不混亂的，那么下邊就需要討論混亂的牌的混亂程度怎么計算。

繼續討論之前，首先我們定義一個新的名詞——混亂度[Degree of Chaos]（無序度），記為Ch。這個概念類似于物理學中的熵。然后，我們把牌抽象為一個一維數組，數組初始值是按照自然數有序的，即1、2、3、4、5……這樣，我們討論的問題就變成了對一個無序數組的處理并得到一個混亂度的問題了。混亂度如何定義才比較合適呢？結合上述的洗牌算法，我有個大膽的猜想，給出混亂度的定義：

定義：無序序列通過交換兩個內部元素還原為有序序列需要的最小次數。

這里定義有兩個關鍵點，一個是通過交換兩個元素還原為有序，另一個是最小次數。前者說明了評價無序序列的方式，即通過還原序列為有序進行交換元素，后者說明了若一個序列越混亂則越難還原為有序的序列，需要的次數越多，同時包含了還原為升序和降序序列需要的最小次數。

例如：對于序列A=(1,4,2,3,5)，需要交換<3，4>、<2，3>兩次才能還原為有序序列A0=(1,2,3,4,5)。當然還有其他的還原步驟，也可以還原為B0=(5,4,3,2,1)。但是不管怎么還原，需要的步數最好是2，即Ch(A)=2。

雖然能按照這種方式得到混亂度，但是如何通過定量的計算得到混亂度呢？因為這直接關系著程序設計的能否實現的問題。

三、混亂度的計算Ch(A)

計算混亂度之前，首先我們需要思考混亂度的定義。混亂度強調最少交換次數變為有序序列。在算法設計中，排序是很經典的問題了，排序算法數不勝數。我們期待的是能否通過排序算法的計算得到混亂度。既然是最少交換次數，我們首先想到的或許是快速排序算法，畢竟它是目前性能最好的排序算法。但是經過驗證它并不合適，單純的將元素按照中軸元素進行分割只會加大交換次數。然后我們嘗試經典的排序算法——冒泡排序，事實證明也不行，因為冒泡排序每次都要進行交換，做了很多無用功。最后我們會想到選擇排序，它的算法性能并不好，但是經過我們的驗證，它是最可能接近我們期待答案的排序算法。為什么呢？改進后的選擇排序算法思想大致可以這么描述：通過按序將數組的某一個元素與后邊的元素比較，最后拿到最小（大）元素與本身交換，最終達到有序。假設數組大小是N，則根據選擇排序算法，最大的交換次數不會大于N-1（最后一個元素不需要交換）。還拿剛才那個例子，A=(1,4,2,3,5)，按照選擇排序算法，通過交換<4,2>、<4,3>也能達到有序，而且也是2步！看起來選擇算法能計算出我們想要的混亂度，通過下邊的實驗可以求出任意序列的混亂度，并能進一步驗證我們的猜想。

首先，我們需要通過選擇排序計算混亂度。算法大致如下：

//計算數組的混亂程度：無需數組通過交換元素恢復到有序（升序和降序）數組需要的最少交換次數
//暫時使用選擇排序交換的次數進行計算，捎帶驗證
template<class?T>
int?messDegree(const?T?data[],const?unsigned?int?len)
{
????T*upData=new?T[len];//升序數據
????T*downData=new?T[len];//降序數據
????int?degree;//混亂度
????unsigned?int?i,j,upK,downK,upSum=0,downSum=0;
????T?t;
????//拷貝數據
????for(i=0;i<len;i++)
????{
????????upData[i]=downData[i]=data[i];
????}
????//排序計算
????for(i=0;i<len-1;i++)
????{
????????upK=downK=i;
????????for(j=i+1;j<len;j++)
????????{
????????????if(upData[j]<upData[upK])//有更小的
????????????????upK=j;
????????????if(downData[j]>downData[downK])//有更大的
????????????????downK=j;
????????}
????????if(upK!=i)
????????{
????????????t=upData[i];
????????????upData[i]=upData[upK];
????????????upData[upK]=t;
????????????upSum++;//計算升序交換次數
????????}
????????if(downK!=i)
????????{
????????????t=downData[i];
????????????downData[i]=downData[downK];
????????????downData[downK]=t;
????????????downSum++;//計算降序交換次數
????????}
????}
????degree=upSum<downSum?upSum:downSum;//取最小值
????delete[]?upData;
????delete[]?downData;
????return?degree;
}

對通過選擇排序得到的結果是否就是混亂度進行證明并不是很容易，本人知識有限，希望有高人出現幫我證明這個命題。下邊討論內容的前提是默認選擇排序的方法是正確的。

四、最大混亂度Ch(N)

我們得到了混亂度的計算方法，針對有序序列A0=(1,2,3…)，混亂度Ch(A0)=0。但是對于N維序列A，它的最大的混亂度Ch(N)是多少，這個能否計算呢？要知道，按照混亂度的定義，最大的混亂度代表著序列的最無序的狀態，相應的也就代表牌被洗得不能再洗的情況，所以，最大混亂度有它實際的含義。但是計算最大混亂度目前還沒有比較直接的公式可以使用，既然如此，我們就使用計算機枚舉所有可能的序列來計算一部分最大混亂度。

我們將計算混亂度的算法嵌入到n階排列算法中，于是得到所有的n！個排列對應的混亂度。由于我們只關心最大的混亂度Ch(N)，所以算法只記錄了Ch(N)。

//構造所有排列,求最大需要的交換個數——最大混亂度
template<class?T>
void?perm(T?data[],int?k,int?m,int?&max,int?len)
{
????if(k==m)//一個排列出現
????{
????????int?t=messDegree(data,len);//計算混亂度
????????if(max<t)
????????????max=t;//記錄最大混亂度
????????return?;
????}
????else
????{
????????for(int?i=k;i<=m;i++)
????????{
????????????int?t=data[i];
????????????data[i]=data[k];
????????????data[k]=t;
????????????perm(data,k+1,m,max,len);
????????????t=data[i];
????????????data[i]=data[k];
????????????data[k]=t;
????????}
????}
}

對于N維序列，枚舉出所有的可能序列是個排列問題，時間復雜度是O(n!)。因此算法的復雜度相當高，受限于機器能力，我只測試到N=11時對應的Ch(N)。由于3個元素一下的序列不存在混亂的問題，很明顯Ch(1)=Ch(2)=0。所以討論N≥3情況下的Ch(N)才有實際意義。以下是枚舉所有情況得到的Ch(n):

Ch(3)=1、Ch(4)=3、Ch(5)=4、Ch(6)=4、Ch(7)=5、Ch(8)=7、Ch(9)=8、Ch(10)=8、Ch(11)=9。

得到這個結果其實并不令人滿意，本想從中找到一些規律來更好地計算最大混亂度的希望破滅了。

五、總結

本文從洗牌算法中引申出如何評價洗出的牌質量的方法，首先引入概念——混亂度，然后提出通過按照選擇排序算法進行計算混亂度的猜想，最后使用窮舉的方式求解了簡單的序列的最大混亂度Ch(N)。遺憾的是筆者并沒有給出選擇排序算法計算混亂度是否正確的形式化證明和最大混亂度的簡便計算方法。希望基于筆者的想法，有能人異士幫助筆者幫助解決這兩個問題，必不勝感激！（——Florian fanzhidongyzby@163.com）

?

總結

以上是生活随笔為你收集整理的关于如何评价洗牌质量的猜想的全部內容，希望文章能夠幫你解決所遇到的問題。

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