PQ Tree

http://knol.google.com/k/pq-trees-and-the-consecutive-ones-property

ICPC 3511 UVa 11993

問題描述

N個人，排成一直線。限制某些人一定要排在一起，這樣的限制有許多組，必須同時滿足。問有幾種排法、列出所有排法；如果限制過多，也可能無解。

可以轉化成Consecutive Ones Problem

令一個row代表一個限制，要排一起的人標1。兩個column交換，就等於一直線中的兩個人對調位置，一直交換後，如果每個row各自都能連成連續的1，就形成一組解了！

楊氏矩陣

http://mathworld.wolfram.com/YoungTableau.html