算法合集之p225lya計(jì)數(shù)法的應(yīng)用(編輯修改稿)
2024-11-12 20:29 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 邊的置換，也是類似的。如果把每個(gè)置換都處理一遍，是很浪費(fèi)的。 ?這 3個(gè)，只要處理一個(gè)即可。 分析 ?枚舉出所有本質(zhì)不同的對(duì)于點(diǎn)的置換，并對(duì)每種置換求下面 2個(gè)值 – 該種置換的對(duì)應(yīng)邊的置換的循環(huán)節(jié)數(shù) – 與該種置換類似的置換總數(shù) 分析 ?要保證枚舉出來(lái)的對(duì)于點(diǎn)的置換各不相同，只需枚舉它的所有循環(huán)節(jié)長(zhǎng)度，設(shè)為 Li，并保證 ?0＜ L1≤L2≤… ≤Lm ?L1+L2+… +Lm=N ?N=53時(shí)，一共要需要枚舉 329921種不同情況。 分析 ? 然后需要把對(duì)應(yīng)點(diǎn)的循環(huán)信息轉(zhuǎn)化成對(duì)應(yīng)邊的置換的循環(huán)節(jié)數(shù) 分析 ? 假設(shè)點(diǎn) i與點(diǎn) j同屬于一個(gè)長(zhǎng)度為 L的循環(huán)中， 則 (i,j)組成的置換中循環(huán)節(jié)個(gè)數(shù)為 ?有一個(gè)長(zhǎng)度為 5的循環(huán) (1,2,3,4,5) ?(1,2),(2,3),(3,4),(4,5),(5,1) ?(1,3),(2,4),(3,5),(4,1),(5,2) ??????2L分析 ? 假設(shè)點(diǎn) i與點(diǎn) j各屬于長(zhǎng) L1和 L2的兩個(gè)不同循環(huán)中，則這樣的邊 (i,j)組成的置換中循環(huán)節(jié)個(gè)數(shù)為(L1,L2)。 ?(1,2) (3,4,5,6) ?(1,3),(2,4),(1,5),(2,6) ?(1,4),(2,5),(1,6),(2,3) 分析 ?還需要求出與其類似的置換數(shù) ?假設(shè)已確定了 0＜ L1≤L2≤… ≤Lm ，接下來(lái)就是將 1… N這 N個(gè)點(diǎn)分別放入這 m個(gè)循環(huán)節(jié)中，滿足第 i個(gè)循環(huán)中恰含有 Li個(gè)點(diǎn)，這相當(dāng)于 m個(gè)圓排列問題，可知一共有 mLLLN...!21 種不同方式。 分析 ?如果有 Li=Li+1=… =Lj，那么每 (ji+1)!種方案又是重復(fù)的，所以還要除以 (ji+1)! 分析 ?所以總的置換個(gè)數(shù)就是 ?每個(gè)循環(huán)的長(zhǎng)度為 L ?每組 Li
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1