2010年10月21日 星期四

Mathematica研究:rookPolynomial

rookPolynomial[list_] :=
Plus @@ Flatten@
Apply[Times,
Flatten[list //. {a_ /; Union@Flatten@a == {1, x} :> a,
{{{a_, c_}}, b___} :> {b, {{1}}, {{x}}},
{a : {{x} ..}, b___} :> {b, a},
{{b_, d___}, c___} :> {c, {d},
Append[Select[{d},
Length[#] <
2 || (#[[1]] != b[[1]] && #[[2]] !=
b[[2]]) &], {x}]}}, {3}], {2}]


以上是mathematica的code。這演算法特別適合rule based的寫法,寫出來很簡潔。使用方法:
rookPolynomial[{{{1,1},{1,2},{1,3},{2,1},{2,2}}}],數字是格子座標,視為矩陣的index。

西洋棋中的城堡可直行橫行,在任意形狀的棋盤上放置數個城堡,如果這些城堡不互相攻擊,則每個城堡必須彼此不在同行同列上。rook polynomial就是每種排列法的生成函數,特別適合用來解決有限制的排列問題(或稱瓶頸指派問題)。例如八個人排成一列,甲不排1,3,5位,乙不排2,3,4位之類的,或是更複雜的問題(例如不規則的棋盤形狀),這種問題在高中時通常是用排容原理來計算,但是限制位數一多,或是棋盤形狀非常不規則,那排容原理會顯的非常繁雜,這時rook polynomial就可派上用場了。

值得注意的是,如果沒有禁止的位置,棋盤形狀是正方形,那是有公式可計算的。手動計算rook polynomial時,可以做行列交換換得一個更容易計算的棋盤,上面的程式就沒那麼聰明,不過基於電腦運算的快速,還是會比手算來得快上許多。詳細情況可以查找離散數學的教科書,或是wiki,上面的程式可以幫助你檢驗答案。實作時,如果禁位少,也可利用直接對禁位作rook polynomial,再利用排容原理計算。

沒有留言: