対称群（置換群）の規約表現はヤング図で表わされますが、各々の置換も、標準ヤング盤二個の組で表すことができます。その組は 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
