note.txt

tongji acm-online judge solution

{
                [1 2 3 4
                |     /
        [1 2 3 -[1 2 4 3
        |    |  |   /
        |    |  [1 4 2 3
        |    |  | /
        |    |  [3 1 2 3
        |    |
        |    |  [4 1 3 2 
        |   /   | \
  [1 2 -[1 3 2 -[1 4 3 2 
  |     |  |    |   \
  |     |  |    [1 3 4 2
  |     |  |    |     \
  |     |  |    [1 3 2 4
  |     |  |    
  |     |  |    [3 1 2 4
  |     | /     |     /
  |     [3 1 2 -[3 1 4 2 
  |             |   /
  |             [3 4 1 2 
  |             | /
  |             [4 3 1 2
1-[          
  |             [4 3 2 1
  |             | \   
  |     [3 2 1 -[3 4 2 1
  |     | \     |   \
  |     |  |    [3 2 4 1
  |     |  |    |     \
  |     |  |    [3 2 1 4
  |     |  |
  |     |  |    [2 3 1 4
  |     |  |    |     /
  [2 1 -[2 3 1 -[2 3 4 1 
        |  |    |   /
        |  |    [2 4 3 1
        |  |    | /  
        |  |    [4 2 3 1
        |  |    
        |  |    [4 2 1 3
        |   \   | \
        [2 1 3 -[2 4 1 3
                |   \
                [2 1 4 3 
                |     \
                [2 1 3 4

以上列出了4层搜索树,第i层是i的全排列.
观察发现第i层就是把第i-1层的父亲在每个位置上都插入i一次.
有左向右插入,右向左插入两种方式,这是根据第i-1层的父亲的在i-1中的全排列的序数的奇偶性.

令f(i)为i在排列P里数字i前有多少个数字j(j<i).
令p(i)为在当前层有几个排列现于当前排列.
(i)
令m=第i-1层的父亲的在i-1中的全排列的序数
m奇偶性的奇偶性决定插入方式 
若m为奇数p(i)=i-1-f(i),若m为偶数p(i)=f(i)
这里
m=p(1)*2*3*..i+..+p(i-2)*(i-1)*i+p(i-1)*i+p(i)
(ii)
在第i层在当前排列前有p(i)个兄弟所生成的排列(有p(i)*(i+1)*(i+2)*n个)在给定排列P前.