目前大家應(yīng)該是對(duì)排列組合怎么算（排列組合算法真厲害）比較感興趣的，所以今天好房網(wǎng)小編CC就來為大家整理了一些關(guān)于排列組合怎么算（排列組合算法真厲害）方面的相關(guān)知識(shí)來分享給大家，希望大家會(huì)喜歡哦。

排列組合怎么算（排列組合算法真厲害）

需求

最近工作中碰到一個(gè)需求：我們的數(shù)據(jù)表有多個(gè)維度，任意多個(gè)維度組合后進(jìn)行 group by 可能會(huì)產(chǎn)生一些”奇妙”的反應(yīng)，由于不確定怎么組合，就需要將所有的組合都列出來進(jìn)行嘗試。

抽象一下就是從一個(gè)集合中取出任意元素，形成唯一的組合。如 [a,b,c] 可組合為 [a]、[b]、[c]、[ab]、[bc]、[ac]、[abc]。

要求如下：

組合內(nèi)的元素?cái)?shù)大于 0 小于等于 數(shù)組大??；

組合內(nèi)不能有重復(fù)元素，如 [aab] 是不符合要求的組合；

組合內(nèi)元素的位置隨意，即 [ab] 和 [ba] 視為同一種組合；

看到這里，就應(yīng)該想到高中所學(xué)習(xí)的排列組合了，同樣是從集合中取出元素形成一個(gè)另一個(gè)集合，如果集合內(nèi)元素位置隨意，就是組合，從 b 個(gè)元素中取 a 個(gè)元素的組合有 種。而如果要求元素順序不同也視為不同集合的話，就是排列，從 m 個(gè)元素取 n 個(gè)元素的排列有 種。

我遇到的這個(gè)需求就是典型的組合，用公式來表示就是從元素個(gè)數(shù)為 n 的集合中列出 種組合。

文中算法用Java實(shí)現(xiàn)。

從排列到組合-窮舉

對(duì)于這種需求，首先想到的當(dāng)然是窮舉。由于排列的要求較少，實(shí)現(xiàn)更簡(jiǎn)單一些，如果我先找出所有排列，再剔除由于位置不同而重復(fù)的元素，即可實(shí)現(xiàn)需求。假設(shè)需要從 [A B C D E] 五個(gè)元素中取出所有組合，那么我們先找出所有元素的全排列，然后再將類似 [A B] 和 [B A] 兩種集合去重即可。

我們又知道 ，那么我們先考慮一種情況 ，假設(shè)是 ，從 5 個(gè)元素中選出三個(gè)進(jìn)行全排列。

被選取的三個(gè)元素，每一個(gè)都可以是 ABCDE 之一，然后再排除掉形成的集合中有重復(fù)元素的，就是 5 選 3 的全排列了。

代碼是這樣：

對(duì)于結(jié)果組合的排重，我借用了 Java 中 HashSet 的兩個(gè)特性：

元素唯一性，選取三個(gè)元素放到 Set 內(nèi)，重復(fù)的會(huì)被過濾掉，那么就可以通過集合的大小來判斷是否有重復(fù)元素了，

元素?zé)o序性，Set[A B] 和 Set[B A] 都會(huì)被表示成 Set[A B]。另外又由于元素唯一性，被同時(shí)表示為 Set[A B] 的多個(gè)集合只會(huì)保留一個(gè)，這樣就可以幫助將全排列轉(zhuǎn)為組合?？梢宰⒁獾玫剑厦娉绦蛑?count 參數(shù)是寫死的，如果需要取出 4 個(gè)元素的話就需要四層循環(huán)嵌套了，如果取的元素個(gè)取是可變的話，普通的編碼方式就不適合了。

注: 可變層數(shù)的循環(huán)可以用 遞歸 來實(shí)現(xiàn)。

從排列到組合-分治

窮舉畢竟太過暴力，我們來通過分治思想來重新考慮一下這個(gè)問題：

分治思想

分治的思想總的來說就是”大事化小，小事化了”，它將復(fù)雜的問題往簡(jiǎn)單劃分，直到劃分為可直接解決的問題，再?gòu)倪@個(gè)直接可以解決的問題向上聚合，最后解決問題。

從 M 個(gè)元素中取出 N 個(gè)元素整個(gè)問題很復(fù)雜，用分治思想就可以理解為：

首先，如果我們已經(jīng)從 M 中元素取出了一個(gè)元素，那么集合中還剩下 M-1 個(gè)，需要取的元素就剩下 N-1 個(gè)。還不好解決的話，我們假設(shè)又從 M-1 中取出了一個(gè)元素，集合中還剩下 M-2 個(gè)，需要取的元素只剩下 N-2 個(gè)。直到我們可能取了有 M-N+1 次，需要取的元素只剩下一個(gè)了，再?gòu)氖Ｓ嗉现腥。褪且粋€(gè)簡(jiǎn)單問題了，很簡(jiǎn)單，取法有 M-N+1 種。如果我們解決了這個(gè)問題，已經(jīng)取完最后一次了產(chǎn)生了 M-N+1 種臨時(shí)集合，再考慮從 M-N+2 個(gè)元素中取一個(gè)元素呢，又有 M-N+2 種可能。將這些可能聚合到一塊，直到取到了 N 個(gè)元素，這個(gè)問題也就解決了。

還是從 5 個(gè)元素中取 3 個(gè)元素的示例：

從 5 個(gè)元素中取 3 個(gè)元素是一個(gè)復(fù)雜問題，為了簡(jiǎn)化它，我們認(rèn)為已經(jīng)取出了一個(gè)元素，還要再?gòu)氖Ｓ嗟?4 個(gè)元素中取出 2 個(gè)，求解公式為：。從 4 個(gè)元素中取出 2 個(gè)依舊不易解決，那我們?cè)偌僭O(shè)又取出了一個(gè)元素，接下來的問題是如何從 3 個(gè)元素中取一個(gè)，公式為 。從 3 個(gè)元素中取 1 個(gè)已經(jīng)是個(gè)簡(jiǎn)單問題了，有三種可能，再向上追溯，與四取一、五取一的可能性做乘，從而解決這個(gè)問題。代碼實(shí)現(xiàn)

用代碼實(shí)現(xiàn)如下：

其實(shí)就是 遞歸。

直擊本質(zhì)-位運(yùn)算

從元素的全排列找全組合，比窮舉略好，但還不是最好的方法，畢竟它”繞了一次道”。

很多算法都能通過位運(yùn)算巧秒地解決，其優(yōu)勢(shì)主要有兩點(diǎn)：一者位運(yùn)算在計(jì)算機(jī)中執(zhí)行效率超高，再者由于位運(yùn)算語(yǔ)義簡(jiǎn)單，算法大多直指本質(zhì)。

組合算法也能通過位運(yùn)算實(shí)現(xiàn)。

思想

再次考慮全組合的需求，從 M 個(gè)元素中取任意個(gè)元素形成組合，組合內(nèi)元素不能重復(fù)、元素位置無關(guān)。

之前的方法都是從結(jié)果組合是否滿足要求來考慮問題，考慮組合是否有重復(fù)元素、是否已有同樣的組合等條件。如果換種思路，從待選元素上來考慮呢？

對(duì)于每個(gè)元素來說，它的狀態(tài)就簡(jiǎn)單得多了，要么被放進(jìn)組合，要么不放進(jìn)組合。每個(gè)元素都有這么兩種狀態(tài)。如果從 5 個(gè)元素中任意取 N 個(gè)元素形成組合的話，用二進(jìn)制位來表示每個(gè)元素是否被放到組合里，就是：

看到這里，應(yīng)該就非常清楚了吧，每種組合都可以拆解為 N 個(gè)二進(jìn)制位的表達(dá)形式，而每個(gè)二進(jìn)制組合同時(shí)代表著一個(gè)十進(jìn)制數(shù)字，所以每個(gè)十進(jìn)制數(shù)字都就能代表著一種組合。

十進(jìn)制數(shù)字的數(shù)目我們很簡(jiǎn)單就能算出來，從00000... 到 1111.. 一共有 種，排除掉全都不被放進(jìn)組合這種可能，結(jié)果有種。

---

版權(quán)說明： 本文由用戶上傳，如有侵權(quán)請(qǐng)聯(lián)系刪除！

---

標(biāo)簽：