catalog

• 圓排列
• • size為n的圓排列
  • size為m的圓排列
  • 對稱圓排列
• 斯特林數 - 第一類
• • 例題

圓排列

圓排列 又稱循環排列，他是一個“二維形狀”，構成空間上的一個 圓形每個圓排列，都對應有“多個”直線排列比如，某個圓排列的size是4，那么他就有4個“直線排列”因為，比如某個直線排列是abcd' 所謂圓排列，即把abcd這個直線排列，“均勻”的放到一個圓上 ' 那么，這個圓排列 所對應的直線排列有： abcd、bcda 、cdab 、dabc “即，圓排列看的是： 這n個元素間的 相對位置 ”2個圓排列相同：1， 元素個數相同2， 這n個元素 的 相對問題，都相同 a de b 和 c e ， 這倆是 同個 圓排列d c b a

size為n的圓排列

從n個元素中，選出一個“size為n”的圓排列，問能得到多少種不同的圓排列。比如n=4：第1個圓排列： abcd、bcda、cdab、dabc ' 這都對應同一個圓排列 '第2個圓排列： abdc、bdca、cabd、dcab ' 這都對應同一個圓排列 '第3個圓排列： acbd、b...、c...、d...第4個圓排列： acdb、b...、c...、d...第5個圓排列： adbc、b...、c...、d...第6個圓排列： adcb、b...、c...、d...方式1：1個全圓排列（size=n） 對應 n個直線排列而，n個元素 有n!個直線排列 故，有 n! / n = (n-1)! 個 全圓排列方式2：每個圓排列，他所對應的“直線排列”，都是n個形如：“a...、b...、c...、d...”所以，只看第一個a... 則有(n-1)! 個全圓排列

size為m的圓排列

從n個元素中，選出一個“size為m”的圓排列，問能得到多少種不同的圓排列。比如n=4、m=3：第1個圓排列： abc、b..、c.. ' 這都對應同一個圓排列 '第2個圓排列： acb、c..、b.. ' 這都對應同一個圓排列 '第3個圓排列： abd、b..、d..第4個圓排列： adb、........第5個圓排列： acd、........第6個圓排列： adc、........第7個圓排列： bcd、cdb、dbc ' 注意這里非常重要！！ 與上面不同 '第8個圓排列： bdc、dcb、cbd ' 這2項是沒有a元素的！！ 你很容易把這2給忘掉... 'n個元素 他有A(n, m)個 “長度為m的 直線排列”，注意別寫成C(n,m) 這個A(n,m)，就對應為上面的這么多項！！！ 即，所以長度為m 的排列。 然后3個一組，所以 A(n,m) / m一個size=m的圓排列，他有： m個 長度為m的 直線排列 即這個問題的 圓排列數為： A(n, m) / m

對稱圓排列

在普通的圓排列中， a ae b 和 b e 是不同的圓排列d c c d但是，如果我們規定： 不考慮“順逆時針”（換句話說： 允許 鏡像/對稱 匹配）' 上面兩個圖形， 是“鏡像”對稱的。 所以，屬于同個 對稱圓排列 '即，鏡像對稱左L： 有m個 圓排列鏡像對稱右R： 有m個 圓排列 ' 注： L和R 不是同個 圓排列 '故，在普通的基礎上， 多了2倍， 只需在求圓排列后， 除以2即可 故：n個元素，有： A(n, m) / m / 2個 （size=m的）對稱圓排列

斯特林數 - 第一類

將n個元素，劃分成 m個 “非空”圓排列 的方案數' 注意，不是選出m個數，而是劃分成m個集合。 即：每種方案，都有n個元素 '' 這m個圓排列之間，不存在排列順序問題 ' 1 <= m <= n 當m = 1： 即把n個數都放入一個圓排列里，對應上面的 size=n的全圓排列問題ans = (n - 1)! 當m = n： 因為是非空，即這n個圓排列 每個里面都有1個元素。 圓排列之間不考慮順序問題ans = 1n=3, m=2（1） （23）（2） （13）（3） （12） n=4, m=2 （1） （234） （1） （243） （2） （134） （2） （143） （3） （124） （3） （143） （4） （123） （4） （132） （12） （34） （13） （24） （14） （23）' 因為，很很重要的一點： 這n個元素 都要參與 每一種的方案里！！！ 并不是選出m個元素 ' ' 劃分成m個集合，n個元素都要參與，所以： 可以考慮dp 'cur = dp[4][2] 第二維度的2表示：此時有2個圓排列：（圓排列1）（圓排列2）我們此時新添加1個元素“第5號元素”: 即從dp[4][2] 往 dp[5][] 轉移元素5，在dp[4][2]的基礎上，新建立一個集合：即dp[5][3]： （圓排列1）（圓排列2）（圓排列3）且，圓排列3 只有1個元素，即這個元素5.dp[n][m] -> dp[n + 1][m + 1] 元素5，在dp[4][2]的基礎上，放到現有集合里面：即dp[5][2]： （圓排列1）（圓排列2）比如元素5 放到圓排列1里面： '此時圓排列1，形態 個數 元素，都是確定的！ 即是某1個方案 '比如圓排列1是： 1 新元素放入： 1x32 13x2 132x 2 3原先的圓排列(a) -> 新加1個元素 -> (ax)原先的圓排列(ab) -> 新加1個元素 -> (axb) (abx)原先的圓排列(abc) -> 新加1個元素 -> (axbc) (abxc) (abcx)原先的圓排列(abcd) -> 新加1個元素 -> (axbcd) (abxcd) (abcxd) (abcdx)' 即，對應某一個 唯一確定的 size=n的 圓排列， 新加1個元素，會有 n種 新的圓排列 '因為這個新元素，可以放到任意兩元素的中間故，這個元素5 放到 dp[4][2]里：dp[4][2] = cont ' 表示，有cont種 方案數 '對于，dp[4][2]里的 “某一個方案”來說： 這個元素5： 放入圓排列1/2里，會產生 (圓排列1的size) + (圓排列2的size)種 方案dp[n][m] * n -> dp[n + 1][m]' 這里的 *n， 其實是： 這m個圓的size 之和 = n '[i - 1][j - 1] 和 [i - 1][j] 更新-> dp[i][j] ' 和排列數公式的dp更新，完全一樣。 ' ' 注意for循環的順序， 即，當到了dp[i][j]時 他的答案必須是正確的！！！'dp[1][1] = 1; FOR(i, 1, n, 1){FOR(j, 1, i, 1){dp[i + 1][j] += (dp[i][j] * i); dp[i + 1][j + 1] += (dp[i][j]);} }

例題

https://leetcode-cn.com/problems/number-of-ways-to-rearrange-sticks-with-k-sticks-visible/給定n和m 有n個數字：1,2,3...,n 將他們排成一排（n!種） 數字代表高度 問，從左側往右側去看，恰好可以看到m個數字 的方案數n=3, m=2 (1 3 2) &nbsp; (2 3 1) &nbsp; (2 1 3)比如，我們令 看到的這m個數字為： (h1, ..都比h1小) (h2, ..都比h2小) (h3 ..都比h3小) ... 自然有：h1 < h2 < h3, ..., < hm方法1：思考“第1類 斯特林數”： (圓排列1) (圓排列2) ...比如圓排列1，他對應的直線排列是： 123, 231, 321比如圓排列2，他對應的直線排列是： 465, 654, 546' 我們選擇， (321) (654) 這種直線排列 '因為，一種圓排列，對應有很多個 直線排列，我們選擇： 以"最大元素"為開頭的 直線排列根據： (h1, ..都比h1小) (h2, ..都比h2小) (h3 ..都比h3小) ...得到： 圓排列1 圓排列2 圓排列3' 任何一種直線排列，唯一對應 1種圓排列！。 1種圓排列，對應很多種 直線排列 '不同的直線排列，可能對應同1個圓排列！！！ 比如： (123) （231） （312） 對應的是： 1種 圓排列但是： 開頭元素相同的直線排列，一定對應不同的 圓排列！！！比如： (312) (321) 他對應的是： 2種 圓排列本題中，h1 < h2 < h3 < .. 的限定， 對應于： 第1類斯特林數中的：不同圓排列 順序無關所以， (312) (321) 在本題中，是不同方案； 在圓排列中，也是不同的圓排列因此，該題 就是 第1類斯特林數方法2：前提是，你必須知道：令看到的這m個數字為： h1 < h2 < h3, ..., hm(h1, ..都比h1小) (h2, ..都比h2小) (h3 ..都比h3小) ...' 以上的這m個集合， size >= 1 '(4, 2, 1, 3) (5) (8, 6, 7) 這是一種方案(4, 3!) (5) (8, 2!) 這3! * 2!個，都是合法的即，每個集合，開頭元素最大，其他元素的可以進行 全排列涉及到“方案數”，一定要想到dp！！！令dp[n][m]為： 將n個元素(1,2,3...,n) 分成 m個集合 的方案數（對應題目的要求）此時，這個dp[n][m]里的每個方案，都滿足：(h1, ..都比h1小..) (h2, ..都比h2小..) (h3 ..都比h3小..) ...當新增(n+1)這個元素1， 這個元素，單獨成1個集合（他只能放到最后，因為(n+1)是最大的元素）dp[n+1][m+1] = dp[n][m]2， 這個元素，放到這m個集合中dp[8][3]: (4, 2, 1, 3) (5) (8, 6, 7)因為這個元素是n+1，是最大的元素！！！！ 所以，他只能 放到第m個 最后的集合中去。即： (4, 123) (5) (9, 678)“其實，這是錯的！！！！”9，確實是只能在最后1個集合里。 但是，9不一定是放到 “原先的最后集合”因為，9放到哪個集合里， 這個集合 立刻就變成了 最后的集合！！！9放到5集合里，他會自動變成： （4, 123） (8, 67) (9, 5)' 即， 這個新元素9，是可以放到 這m個集合里，任意的集合里面的！！！'以，(4, 123)來看， 比如我們將9 放到這個集合里。假如是： dp[nex] = dp[cur]意味著，你只得到了： (9, 4, 3!) = 3!= 6種方案但其實，(9, 4!) 都是合法的。 9的后面，不一定是4，是誰都可以。即，cur的dp中，某個集合是： (最大H， c個<H的全排列) 方案是c!（這是在cur的dp里）現加入一個新元素New，（New > H）如果你直接dp[cur] -> dp[nex]會得到： (New, H, c個<H的全排列)而， 此時，H不一定是 第2個元素，這c個<H的元素，都可以是第2個元素因此是： dp[cur] * (集合size) -> dp[nex]dp[cur] * (集合1的size) -> dp[nex]dp[cur] * (集合2的size) -> dp[nex]dp[cur] * (集合3的size) -> dp[nex]綜合便是： dp[n][m] * n -> dp[n + 1][m]這確實很復雜，最好想到圓排列。1， 新元素n+1，不是只能放到 原先dp的最后一個集合里！！！放到任意一個集合里，都可以。 這很難2， 新元素n+1，放到某個(size)的集合里原先集合里是：(size-1)!的全排列。 而現在集合可以是：(size)!的全排列所以，需要 *= size這個dp定義，很重要。 比如dp[6][2]：(3, 1, 2) (6, 5, 4)(5, 4, 3) (6, 1, 2)(1) (6, 5, 4, 3, 2)' 即，每個集合的開頭元素 不固定，集合大小也不固定！！ '肯定是不固定的，這就是dp的本質。 他就是指的一個“泛化”的形式。一個簡單的dp[6][2]， 包含了很多的具體方案 你可以從，集合大小來看 '因為，這個dp的信息，只有：6個元素，2個集合 '集合的個數是固定的。(1) (5)(2) (4)(3) (3)(4) (2)(5) (1) 這個dp[6][2]，一定由以上的5種分配 組成。

總結

以上是生活随笔為你收集整理的圆排列、循环排列、斯特林数、stirling的全部內容，希望文章能夠幫你解決所遇到的問題。

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