順番付並べ替えの列挙

１からｎまでの整数の順番付並べ替えを、再帰を使って列挙します。

実行結果

ソース・プログラム

[list1, list2(i)], pack(list2, list2 /= list2(i)) この行では、list2　から要素を一個取り出して消して、list1 に加えています。配列をリストとして用いています。
[integer::]は整数型の大きさ 0 の配列です。空リストの代用として使っています。
関数呼び出しのスタックを活用しているので、再帰呼び出しから帰ってくると、元のリストが保たれており、バックトラックが容易に実現されます。

module m_interleave
contains
  recursive subroutine interleave(list1, list2)
    integer, intent(in) :: list1(:), list2(:)
    integer :: i
    if (size(list2) == 0) then
      print '(25i3)', list1
    else
      do i = 1, size(list2)
        call interleave( [list1, list2(i)], pack(list2, list2 /= list2(i)) )        
      end do
    end if
    return
  end subroutine interleave

end module m_interleave  

program backtrack
  use m_interleave
  call interleave([integer::], [1:4])
  stop
end program backtrack