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