fortran66のブログ

fortran について書きます。

整数の分割数 p(n) 再び

以前整数の分割を扱いましたが、OOP風に整理しなおしたものを載せておきます。

サイズの決まらない配列の配列を実現するために、派生型の配列を取り、それをいちいち割り付けしなおす方法を取りました。ポインタで次要素をさしてもいいのですが、解放が面倒なのと量が少ないのでこれで行くこととします。

分割は素朴には全順序にならず、木型の分岐構造の半順序の形になっているので、再帰で枝を辿って生成し、配列に積んでいきます。辞書的な並びで整列されることになります。

module m_partition
    implicit none
    type :: t_part
      integer, allocatable :: l(:)  
    end type t_part
    
    type :: t_partition
      type (t_part), allocatable :: q(:)
    contains
      procedure :: make => mk_partition
      procedure :: size => sz_partition
      procedure :: pr   => pr_partition
    end type t_partition
    
contains
    subroutine mk_partition(p, n)
      class (t_partition), intent(out) :: p
      integer, intent(in) :: n
      allocate(p%q(0))              ! p%q <= null()
      call parti([integer::], n, n) ! [integer::] zero-sized integer array 
      return
    contains
      recursive subroutine parti(list, n, n0)
        integer, intent(in) :: list(:), n, n0
        type (t_part), allocatable :: tmp(:)
        integer :: i
        if (n == 0) then            ! push result to p 
          tmp = [p%q, t_part(list)]
          call move_alloc(tmp, p%q)
        else 
          do i = n - n0, n - 1
            call parti([list, n - i], i, min(i, n - i))
          end do
        end if
        return
      end subroutine parti
    end subroutine mk_partition 

    integer function sz_partition(p)
      class (t_partition), intent(in) :: p
      sz_partition = size(p%q)
      return
    end function sz_partition
    
    subroutine pr_partition(p)
      class (t_partition), intent(in) :: p
      integer :: i
      do i = 1, p%size()
        print '(25i3)', p%q(i)%l
      end do  
      return
    end subroutine pr_partition
    
end module m_partition
    
program part
    use m_partition
    implicit none
    type (t_partition) :: partition 
    integer :: n
    do n = 1, 20
      call partition%make(n)
      print *, 'the number of partitions of ', n, ' = ', partition%size()
      call partition%pr()
    end do
    stop
end program part