fortran66のブログ

fortran について書きます。

Robinson-Schensted correspondence

対称群置換群)の規約表現はヤング図で表わされますが、各々の置換も、標準ヤング盤二個の組で表すことができます。その組は Robinson と Schensted による非常に単純なアルゴリズムに依って求められます。その求め方は bumping とも言われますが、次々とヤング図に数字が入ってきては、先に入った数字が追し出される様を表した言葉です。
ここでは、その組を求めるプログラムを作ります。1〜n の数字が permutation によって並べ替えられる置換に対する標準ヤング盤の組を出力しています。

実行結果

とりあえず |λ| = 9 までは、ちゃんと結果が出ているようでした。以下 |λ| = 1〜3 の結果.

λ = 1
 permutation = 1
  1    1
λ = 2
 permutation = 1 2
  1 2    1 2

 permutation = 2 1
  1      1
  2      2
λ = 3
 permutation = 1 2 3
  1 2 3    1 2 3

 permutation = 1 3 2
  1 2      1 2
  3        3

 permutation = 2 1 3
  1 3      1 3
  2        2

 permutation = 2 3 1
  1 3      1 2
  2        3

 permutation = 3 1 2
  1 2      1 3
  3        2

 permutation = 3 2 1
  1        1
  2        2
  3        3

ソース・プログラム

考えなしに書き始めたので肥大化してしまった・・いずれ整理する!

module m_Robinson_Schensted
  implicit none
  type :: t_box
    integer :: k, ix, iy
  end type t_box
contains
  function bumps(l)
    integer, intent(in) :: l(:)
    type (t_box), allocatable :: bumps(:)
    integer :: i
    allocate(bumps(0))
    do i = 1, size(l)
      bumps = bump(size(l), l(i), bumps)
    end do
    return
  end function bumps

  function bump(n, k0, list)
    integer, intent(in) :: n, k0
    type(t_box), intent(in) :: list(:)
    type(t_box), allocatable :: bump(:)
    integer :: board(n + 1, n + 1)
    integer :: i, k, ix, iy
    board = 0
    do i = 1, size(list)
      board(list(i)%ix, list(i)%iy) = list(i)%k
    end do
    ix = 1
    iy = 1
    k = k0
    bump = list
    do
      if (board(ix, iy) == 0) then
        board(ix, iy) = k
        bump = [ bump, t_box(k, ix, iy) ]
        exit
      else if (board(ix, iy) < k) then
        ix = ix + 1
      else
        i = board(ix, iy)
        board(ix, iy) = k
        bump( findbox(ix, iy, bump) )%k = k
        k = i
        ix = 1
        iy = iy + 1
      end if
    end do
    return
  contains
    integer function findbox(ix, iy, list)
      integer, intent(in) :: ix, iy
      type (t_box), intent(in) :: list(:)
      integer :: i
      do i = 1, size(list)
        if (list(i)%ix == ix .and. list(i)%iy == iy) then
          findbox = i
          exit
        end if
        findbox = 0 ! error
      end do
    end function findbox
  end function bump

  subroutine pr_Robinson_Schensted(list)
    implicit none
    type(t_box), intent(in) :: list(:)
    integer, allocatable :: p(:, :), q(:, :)
    character(len = 132) :: text
    integer :: i, j, n
    n = size(list)
    allocate( p(n, n), q(n, n) )
    p = 0
    q = 0
    do i = 1, size(list)
      p(list(i)%ix, list(i)%iy) = list(i)%k
      q(list(i)%ix, list(i)%iy) = i
    end do
    do i = 1, n
      if ( all(p(:, i) == 0) ) exit
      write(text           , '(*(i2))') pack(p(:, i), p(:, i) /= 0) ! P
      write(text(4 + 2 * n:), '(*(i2))') pack(q(:, i), q(:, i) /= 0) ! Q
      print *, trim(text)
    end do
    print *
    return
  end subroutine pr_Robinson_Schensted

  recursive subroutine permutation(list1, list2)
    integer, intent(in) :: list1(:), list2(:)
    integer :: i
    if (size(list2) == 0) then
      write(9, *) list1
    else
      do i = 1, size(list2)
        call permutation( [list1, list2(i)], pack(list2, list2 /= list2(i)) )
      end do
    end if
    return
  end subroutine permutation

end module m_Robinson_Schensted

program RS
  use m_Robinson_Schensted
  implicit none
  integer, parameter :: n = 3
  integer :: i, io, l(n)
  type (t_box), allocatable :: list(:)
  call permutation([integer::], [1:n]) ! non-standard [1:n] = [(i, i = 1, n)]
  rewind(9)
  do
    read(9, *, iostat = io) l
    if (io == -1) exit
    print *, 'permutation =', l
    call pr_Robinson_Schensted( bumps(l) )
  end do
  stop
end program RS

実行結果 補足

λ = 4
 permutation = 1 2 3 4
  1 2 3 4    1 2 3 4

 permutation = 1 2 4 3
  1 2 3      1 2 3
  4          4

 permutation = 1 3 2 4
  1 2 4      1 2 4
  3          3

 permutation = 1 3 4 2
  1 2 4      1 2 3
  3          4

 permutation = 1 4 2 3
  1 2 3      1 2 4
  4          3

 permutation = 1 4 3 2
  1 2        1 2
  3          3
  4          4

 permutation = 2 1 3 4
  1 3 4      1 3 4
  2          2

 permutation = 2 1 4 3
  1 3        1 3
  2 4        2 4

 permutation = 2 3 1 4
  1 3 4      1 2 4
  2          3

 permutation = 2 3 4 1
  1 3 4      1 2 3
  2          4

 permutation = 2 4 1 3
  1 3        1 2
  2 4        3 4

 permutation = 2 4 3 1
  1 3        1 2
  2          3
  4          4

 permutation = 3 1 2 4
  1 2 4      1 3 4
  3          2

 permutation = 3 1 4 2
  1 2        1 3
  3 4        2 4

 permutation = 3 2 1 4
  1 4        1 4
  2          2
  3          3

 permutation = 3 2 4 1
  1 4        1 3
  2          2
  3          4

 permutation = 3 4 1 2
  1 2        1 2
  3 4        3 4

 permutation = 3 4 2 1
  1 4        1 2
  2          3
  3          4

 permutation = 4 1 2 3
  1 2 3      1 3 4
  4          2

 permutation = 4 1 3 2
  1 2        1 3
  3          2
  4          4

 permutation = 4 2 1 3
  1 3        1 4
  2          2
  4          3

 permutation = 4 2 3 1
  1 3        1 3
  2          2
  4          4

 permutation = 4 3 1 2
  1 2        1 4
  3          2
  4          3

 permutation = 4 3 2 1
  1          1
  2          2
  3          3
  4          4
λ = 5
 permutation = 1 2 3 4 5
  1 2 3 4 5    1 2 3 4 5

 permutation = 1 2 3 5 4
  1 2 3 4      1 2 3 4
  5            5

 permutation = 1 2 4 3 5
  1 2 3 5      1 2 3 5
  4            4

 permutation = 1 2 4 5 3
  1 2 3 5      1 2 3 4
  4            5

 permutation = 1 2 5 3 4
  1 2 3 4      1 2 3 5
  5            4

 permutation = 1 2 5 4 3
  1 2 3        1 2 3
  4            4
  5            5

 permutation = 1 3 2 4 5
  1 2 4 5      1 2 4 5
  3            3

 permutation = 1 3 2 5 4
  1 2 4        1 2 4
  3 5          3 5

 permutation = 1 3 4 2 5
  1 2 4 5      1 2 3 5
  3            4

 permutation = 1 3 4 5 2
  1 2 4 5      1 2 3 4
  3            5

 permutation = 1 3 5 2 4
  1 2 4        1 2 3
  3 5          4 5

 permutation = 1 3 5 4 2
  1 2 4        1 2 3
  3            4
  5            5

 permutation = 1 4 2 3 5
  1 2 3 5      1 2 4 5
  4            3

 permutation = 1 4 2 5 3
  1 2 3        1 2 4
  4 5          3 5

 permutation = 1 4 3 2 5
  1 2 5        1 2 5
  3            3
  4            4

 permutation = 1 4 3 5 2
  1 2 5        1 2 4
  3            3
  4            5

 permutation = 1 4 5 2 3
  1 2 3        1 2 3
  4 5          4 5

 permutation = 1 4 5 3 2
  1 2 5        1 2 3
  3            4
  4            5

 permutation = 1 5 2 3 4
  1 2 3 4      1 2 4 5
  5            3

 permutation = 1 5 2 4 3
  1 2 3        1 2 4
  4            3
  5            5

 permutation = 1 5 3 2 4
  1 2 4        1 2 5
  3            3
  5            4

 permutation = 1 5 3 4 2
  1 2 4        1 2 4
  3            3
  5            5

 permutation = 1 5 4 2 3
  1 2 3        1 2 5
  4            3
  5            4

 permutation = 1 5 4 3 2
  1 2          1 2
  3            3
  4            4
  5            5

 permutation = 2 1 3 4 5
  1 3 4 5      1 3 4 5
  2            2

 permutation = 2 1 3 5 4
  1 3 4        1 3 4
  2 5          2 5

 permutation = 2 1 4 3 5
  1 3 5        1 3 5
  2 4          2 4

 permutation = 2 1 4 5 3
  1 3 5        1 3 4
  2 4          2 5

 permutation = 2 1 5 3 4
  1 3 4        1 3 5
  2 5          2 4

 permutation = 2 1 5 4 3
  1 3          1 3
  2 4          2 4
  5            5

 permutation = 2 3 1 4 5
  1 3 4 5      1 2 4 5
  2            3

 permutation = 2 3 1 5 4
  1 3 4        1 2 4
  2 5          3 5

 permutation = 2 3 4 1 5
  1 3 4 5      1 2 3 5
  2            4

 permutation = 2 3 4 5 1
  1 3 4 5      1 2 3 4
  2            5

 permutation = 2 3 5 1 4
  1 3 4        1 2 3
  2 5          4 5

 permutation = 2 3 5 4 1
  1 3 4        1 2 3
  2            4
  5            5

 permutation = 2 4 1 3 5
  1 3 5        1 2 5
  2 4          3 4

 permutation = 2 4 1 5 3
  1 3 5        1 2 4
  2 4          3 5

 permutation = 2 4 3 1 5
  1 3 5        1 2 5
  2            3
  4            4

 permutation = 2 4 3 5 1
  1 3 5        1 2 4
  2            3
  4            5

 permutation = 2 4 5 1 3
  1 3 5        1 2 3
  2 4          4 5

 permutation = 2 4 5 3 1
  1 3 5        1 2 3
  2            4
  4            5

 permutation = 2 5 1 3 4
  1 3 4        1 2 5
  2 5          3 4

 permutation = 2 5 1 4 3
  1 3          1 2
  2 4          3 4
  5            5

 permutation = 2 5 3 1 4
  1 3 4        1 2 5
  2            3
  5            4

 permutation = 2 5 3 4 1
  1 3 4        1 2 4
  2            3
  5            5

 permutation = 2 5 4 1 3
  1 3          1 2
  2 4          3 5
  5            4

 permutation = 2 5 4 3 1
  1 3          1 2
  2            3
  4            4
  5            5

 permutation = 3 1 2 4 5
  1 2 4 5      1 3 4 5
  3            2

 permutation = 3 1 2 5 4
  1 2 4        1 3 4
  3 5          2 5

 permutation = 3 1 4 2 5
  1 2 5        1 3 5
  3 4          2 4

 permutation = 3 1 4 5 2
  1 2 5        1 3 4
  3 4          2 5

 permutation = 3 1 5 2 4
  1 2 4        1 3 5
  3 5          2 4

 permutation = 3 1 5 4 2
  1 2          1 3
  3 4          2 4
  5            5

 permutation = 3 2 1 4 5
  1 4 5        1 4 5
  2            2
  3            3

 permutation = 3 2 1 5 4
  1 4          1 4
  2 5          2 5
  3            3

 permutation = 3 2 4 1 5
  1 4 5        1 3 5
  2            2
  3            4

 permutation = 3 2 4 5 1
  1 4 5        1 3 4
  2            2
  3            5

 permutation = 3 2 5 1 4
  1 4          1 3
  2 5          2 5
  3            4

 permutation = 3 2 5 4 1
  1 4          1 3
  2 5          2 4
  3            5

 permutation = 3 4 1 2 5
  1 2 5        1 2 5
  3 4          3 4

 permutation = 3 4 1 5 2
  1 2 5        1 2 4
  3 4          3 5

 permutation = 3 4 2 1 5
  1 4 5        1 2 5
  2            3
  3            4

 permutation = 3 4 2 5 1
  1 4 5        1 2 4
  2            3
  3            5

 permutation = 3 4 5 1 2
  1 2 5        1 2 3
  3 4          4 5

 permutation = 3 4 5 2 1
  1 4 5        1 2 3
  2            4
  3            5

 permutation = 3 5 1 2 4
  1 2 4        1 2 5
  3 5          3 4

 permutation = 3 5 1 4 2
  1 2          1 2
  3 4          3 4
  5            5

 permutation = 3 5 2 1 4
  1 4          1 2
  2 5          3 5
  3            4

 permutation = 3 5 2 4 1
  1 4          1 2
  2 5          3 4
  3            5

 permutation = 3 5 4 1 2
  1 2          1 2
  3 4          3 5
  5            4

 permutation = 3 5 4 2 1
  1 4          1 2
  2            3
  3            4
  5            5

 permutation = 4 1 2 3 5
  1 2 3 5      1 3 4 5
  4            2

 permutation = 4 1 2 5 3
  1 2 3        1 3 4
  4 5          2 5

 permutation = 4 1 3 2 5
  1 2 5        1 3 5
  3            2
  4            4

 permutation = 4 1 3 5 2
  1 2 5        1 3 4
  3            2
  4            5

 permutation = 4 1 5 2 3
  1 2 3        1 3 5
  4 5          2 4

 permutation = 4 1 5 3 2
  1 2          1 3
  3 5          2 4
  4            5

 permutation = 4 2 1 3 5
  1 3 5        1 4 5
  2            2
  4            3

 permutation = 4 2 1 5 3
  1 3          1 4
  2 5          2 5
  4            3

 permutation = 4 2 3 1 5
  1 3 5        1 3 5
  2            2
  4            4

 permutation = 4 2 3 5 1
  1 3 5        1 3 4
  2            2
  4            5

 permutation = 4 2 5 1 3
  1 3          1 3
  2 5          2 5
  4            4

 permutation = 4 2 5 3 1
  1 3          1 3
  2 5          2 4
  4            5

 permutation = 4 3 1 2 5
  1 2 5        1 4 5
  3            2
  4            3

 permutation = 4 3 1 5 2
  1 2          1 4
  3 5          2 5
  4            3

 permutation = 4 3 2 1 5
  1 5          1 5
  2            2
  3            3
  4            4

 permutation = 4 3 2 5 1
  1 5          1 4
  2            2
  3            3
  4            5

 permutation = 4 3 5 1 2
  1 2          1 3
  3 5          2 5
  4            4

 permutation = 4 3 5 2 1
  1 5          1 3
  2            2
  3            4
  4            5

 permutation = 4 5 1 2 3
  1 2 3        1 2 5
  4 5          3 4

 permutation = 4 5 1 3 2
  1 2          1 2
  3 5          3 4
  4            5

 permutation = 4 5 2 1 3
  1 3          1 2
  2 5          3 5
  4            4

 permutation = 4 5 2 3 1
  1 3          1 2
  2 5          3 4
  4            5

 permutation = 4 5 3 1 2
  1 2          1 2
  3 5          3 5
  4            4

 permutation = 4 5 3 2 1
  1 5          1 2
  2            3
  3            4
  4            5

 permutation = 5 1 2 3 4
  1 2 3 4      1 3 4 5
  5            2

 permutation = 5 1 2 4 3
  1 2 3        1 3 4
  4            2
  5            5

 permutation = 5 1 3 2 4
  1 2 4        1 3 5
  3            2
  5            4

 permutation = 5 1 3 4 2
  1 2 4        1 3 4
  3            2
  5            5

 permutation = 5 1 4 2 3
  1 2 3        1 3 5
  4            2
  5            4

 permutation = 5 1 4 3 2
  1 2          1 3
  3            2
  4            4
  5            5

 permutation = 5 2 1 3 4
  1 3 4        1 4 5
  2            2
  5            3

 permutation = 5 2 1 4 3
  1 3          1 4
  2 4          2 5
  5            3

 permutation = 5 2 3 1 4
  1 3 4        1 3 5
  2            2
  5            4

 permutation = 5 2 3 4 1
  1 3 4        1 3 4
  2            2
  5            5

 permutation = 5 2 4 1 3
  1 3          1 3
  2 4          2 5
  5            4

 permutation = 5 2 4 3 1
  1 3          1 3
  2            2
  4            4
  5            5

 permutation = 5 3 1 2 4
  1 2 4        1 4 5
  3            2
  5            3

 permutation = 5 3 1 4 2
  1 2          1 4
  3 4          2 5
  5            3

 permutation = 5 3 2 1 4
  1 4          1 5
  2            2
  3            3
  5            4

 permutation = 5 3 2 4 1
  1 4          1 4
  2            2
  3            3
  5            5

 permutation = 5 3 4 1 2
  1 2          1 3
  3 4          2 5
  5            4

 permutation = 5 3 4 2 1
  1 4          1 3
  2            2
  3            4
  5            5

 permutation = 5 4 1 2 3
  1 2 3        1 4 5
  4            2
  5            3

 permutation = 5 4 1 3 2
  1 2          1 4
  3            2
  4            3
  5            5

 permutation = 5 4 2 1 3
  1 3          1 5
  2            2
  4            3
  5            4

 permutation = 5 4 2 3 1
  1 3          1 4
  2            2
  4            3
  5            5

 permutation = 5 4 3 1 2
  1 2          1 5
  3            2
  4            3
  5            4

 permutation = 5 4 3 2 1
  1            1
  2            2
  3            3
  4            4
  5            5