【Fortran】Fortranでnext_permutationを実装する

## 概要
next_permutationはC++のライブラリ(Fortranでいうモジュール)の１つです。
与えられた順列に対して、辞書順で見たときの次の順列を求めることができます。

例えば、(1, 2, 3)という順列を与えると、
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)
が順番に求められます。

上記の様な便利な機能がC++には標準で搭載されていますが、Fortranには同様の機能はありません。
なので自分で書いて実装してみます。


## アルゴリズム
next_permutationは以下に示す４つのステップで構成されています。
配列arr(1)~arr(n)を例に、順列を求める手順を見てみます。
arrは昇順で数字が並んでいるとします。

**STEP 1**
 arr(k) < arr(k + 1)となるようなkの最大値を見つけます。
(ここでkが見つからなければ、次の順列はありません。=　全ての順列が列挙できている。)

**STEP ２**
 arr(k) <  arr(l)となる、kより大きい最大のlを見つけます。

**STEP 3**
arr(k) の値をarr(l)の値を入れ替えます。

**STEP 4** 
arr(k + 1)からarr(n)までを順番を反転して並び替えます。
並び替えたarrが次の順列になります。
次の順列がわかった後には、STEP 1に戻ります。


## 計算例：(1,2,3,4)の場合
色々文字ばかり出ていても分かりにくいので、arr(4)=(1,2,3,4)を例にSTEP１〜４の流れを追ってみます。
<details><summary>【結果】長いので畳んでいます。　</summary>

```
LOOP  1
   STEP  1
      【入力】arr =           1           2           3           4
      k  =  3
   STEP  2
      l  =  4
   STEP  3
      【入れ替え】3 桁目と4 桁目
       arr =           1           2           3           4
       arr =           1           2           4           3
   STEP  4
      【逆順並び替え】4 桁目から4 桁目まで
       arr =           1           2           4           3
       arr =           1           2           4           3
      【出力：】arr =           1           2           4           3
LOOP  2
   STEP  1
      【入力】arr =           1           2           4           3
      k  =  2
   STEP  2
      l  =  4
   STEP  3
      【入れ替え】2 桁目と4 桁目
       arr =           1           2           4           3
       arr =           1           3           4           2
   STEP  4
      【逆順並び替え】3 桁目から4 桁目まで
       arr =           1           3           4           2
       arr =           1           3           2           4
      【出力：】arr =           1           3           2           4
LOOP  3
   STEP  1
      【入力】arr =           1           3           2           4
      k  =  3
   STEP  2
      l  =  4
   STEP  3
      【入れ替え】3 桁目と4 桁目
       arr =           1           3           2           4
       arr =           1           3           4           2
   STEP  4
      【逆順並び替え】4 桁目から4 桁目まで
       arr =           1           3           4           2
       arr =           1           3           4           2
      【出力：】arr =           1           3           4           2
LOOP  4
   STEP  1
      【入力】arr =           1           3           4           2
      k  =  2
   STEP  2
      l  =  3
   STEP  3
      【入れ替え】2 桁目と3 桁目
       arr =           1           3           4           2
       arr =           1           4           3           2
   STEP  4
      【逆順並び替え】3 桁目から4 桁目まで
       arr =           1           4           3           2
       arr =           1           4           2           3
      【出力：】arr =           1           4           2           3
LOOP  5
   STEP  1
      【入力】arr =           1           4           2           3
      k  =  3
   STEP  2
      l  =  4
   STEP  3
      【入れ替え】3 桁目と4 桁目
       arr =           1           4           2           3
       arr =           1           4           3           2
   STEP  4
      【逆順並び替え】4 桁目から4 桁目まで
       arr =           1           4           3           2
       arr =           1           4           3           2
      【出力：】arr =           1           4           3           2
LOOP  6
   STEP  1
      【入力】arr =           1           4           3           2
      k  =  1
   STEP  2
      l  =  4
   STEP  3
      【入れ替え】1 桁目と4 桁目
       arr =           1           4           3           2
       arr =           2           4           3           1
   STEP  4
      【逆順並び替え】2 桁目から4 桁目まで
       arr =           2           4           3           1
       arr =           2           1           3           4
      【出力：】arr =           2           1           3           4
LOOP  7
   STEP  1
      【入力】arr =           2           1           3           4
      k  =  3
   STEP  2
      l  =  4
   STEP  3
      【入れ替え】3 桁目と4 桁目
       arr =           2           1           3           4
       arr =           2           1           4           3
   STEP  4
      【逆順並び替え】4 桁目から4 桁目まで
       arr =           2           1           4           3
       arr =           2           1           4           3
      【出力：】arr =           2           1           4           3
LOOP  8
   STEP  1
      【入力】arr =           2           1           4           3
      k  =  2
   STEP  2
      l  =  4
   STEP  3
      【入れ替え】2 桁目と4 桁目
       arr =           2           1           4           3
       arr =           2           3           4           1
   STEP  4
      【逆順並び替え】3 桁目から4 桁目まで
       arr =           2           3           4           1
       arr =           2           3           1           4
      【出力：】arr =           2           3           1           4
LOOP  9
   STEP  1
      【入力】arr =           2           3           1           4
      k  =  3
   STEP  2
      l  =  4
   STEP  3
      【入れ替え】3 桁目と4 桁目
       arr =           2           3           1           4
       arr =           2           3           4           1
   STEP  4
      【逆順並び替え】4 桁目から4 桁目まで
       arr =           2           3           4           1
       arr =           2           3           4           1
      【出力：】arr =           2           3           4           1
LOOP 10
   STEP  1
      【入力】arr =           2           3           4           1
      k  =  2
   STEP  2
      l  =  3
   STEP  3
      【入れ替え】2 桁目と3 桁目
       arr =           2           3           4           1
       arr =           2           4           3           1
   STEP  4
      【逆順並び替え】3 桁目から4 桁目まで
       arr =           2           4           3           1
       arr =           2           4           1           3
      【出力：】arr =           2           4           1           3
LOOP 11
   STEP  1
      【入力】arr =           2           4           1           3
      k  =  3
   STEP  2
      l  =  4
   STEP  3
      【入れ替え】3 桁目と4 桁目
       arr =           2           4           1           3
       arr =           2           4           3           1
   STEP  4
      【逆順並び替え】4 桁目から4 桁目まで
       arr =           2           4           3           1
       arr =           2           4           3           1
      【出力：】arr =           2           4           3           1
LOOP 12
   STEP  1
      【入力】arr =           2           4           3           1
      k  =  1
   STEP  2
      l  =  3
   STEP  3
      【入れ替え】1 桁目と3 桁目
       arr =           2           4           3           1
       arr =           3           4           2           1
   STEP  4
      【逆順並び替え】2 桁目から4 桁目まで
       arr =           3           4           2           1
       arr =           3           1           2           4
      【出力：】arr =           3           1           2           4
LOOP 13
   STEP  1
      【入力】arr =           3           1           2           4
      k  =  3
   STEP  2
      l  =  4
   STEP  3
      【入れ替え】3 桁目と4 桁目
       arr =           3           1           2           4
       arr =           3           1           4           2
   STEP  4
      【逆順並び替え】4 桁目から4 桁目まで
       arr =           3           1           4           2
       arr =           3           1           4           2
      【出力：】arr =           3           1           4           2
LOOP 14
   STEP  1
      【入力】arr =           3           1           4           2
      k  =  2
   STEP  2
      l  =  4
   STEP  3
      【入れ替え】2 桁目と4 桁目
       arr =           3           1           4           2
       arr =           3           2           4           1
   STEP  4
      【逆順並び替え】3 桁目から4 桁目まで
       arr =           3           2           4           1
       arr =           3           2           1           4
      【出力：】arr =           3           2           1           4
LOOP 15
   STEP  1
      【入力】arr =           3           2           1           4
      k  =  3
   STEP  2
      l  =  4
   STEP  3
      【入れ替え】3 桁目と4 桁目
       arr =           3           2           1           4
       arr =           3           2           4           1
   STEP  4
      【逆順並び替え】4 桁目から4 桁目まで
       arr =           3           2           4           1
       arr =           3           2           4           1
      【出力：】arr =           3           2           4           1
LOOP 16
   STEP  1
      【入力】arr =           3           2           4           1
      k  =  2
   STEP  2
      l  =  3
   STEP  3
      【入れ替え】2 桁目と3 桁目
       arr =           3           2           4           1
       arr =           3           4           2           1
   STEP  4
      【逆順並び替え】3 桁目から4 桁目まで
       arr =           3           4           2           1
       arr =           3           4           1           2
      【出力：】arr =           3           4           1           2
LOOP 17
   STEP  1
      【入力】arr =           3           4           1           2
      k  =  3
   STEP  2
      l  =  4
   STEP  3
      【入れ替え】3 桁目と4 桁目
       arr =           3           4           1           2
       arr =           3           4           2           1
   STEP  4
      【逆順並び替え】4 桁目から4 桁目まで
       arr =           3           4           2           1
       arr =           3           4           2           1
      【出力：】arr =           3           4           2           1
LOOP 18
   STEP  1
      【入力】arr =           3           4           2           1
      k  =  1
   STEP  2
      l  =  2
   STEP  3
      【入れ替え】1 桁目と2 桁目
       arr =           3           4           2           1
       arr =           4           3           2           1
   STEP  4
      【逆順並び替え】2 桁目から4 桁目まで
       arr =           4           3           2           1
       arr =           4           1           2           3
      【出力：】arr =           4           1           2           3
LOOP 19
   STEP  1
      【入力】arr =           4           1           2           3
      k  =  3
   STEP  2
      l  =  4
   STEP  3
      【入れ替え】3 桁目と4 桁目
       arr =           4           1           2           3
       arr =           4           1           3           2
   STEP  4
      【逆順並び替え】4 桁目から4 桁目まで
       arr =           4           1           3           2
       arr =           4           1           3           2
      【出力：】arr =           4           1           3           2
LOOP 20
   STEP  1
      【入力】arr =           4           1           3           2
      k  =  2
   STEP  2
      l  =  4
   STEP  3
      【入れ替え】2 桁目と4 桁目
       arr =           4           1           3           2
       arr =           4           2           3           1
   STEP  4
      【逆順並び替え】3 桁目から4 桁目まで
       arr =           4           2           3           1
       arr =           4           2           1           3
      【出力：】arr =           4           2           1           3
LOOP 21
   STEP  1
      【入力】arr =           4           2           1           3
      k  =  3
   STEP  2
      l  =  4
   STEP  3
      【入れ替え】3 桁目と4 桁目
       arr =           4           2           1           3
       arr =           4           2           3           1
   STEP  4
      【逆順並び替え】4 桁目から4 桁目まで
       arr =           4           2           3           1
       arr =           4           2           3           1
      【出力：】arr =           4           2           3           1
LOOP 22
   STEP  1
      【入力】arr =           4           2           3           1
      k  =  2
   STEP  2
      l  =  3
   STEP  3
      【入れ替え】2 桁目と3 桁目
       arr =           4           2           3           1
       arr =           4           3           2           1
   STEP  4
      【逆順並び替え】3 桁目から4 桁目まで
       arr =           4           3           2           1
       arr =           4           3           1           2
      【出力：】arr =           4           3           1           2
LOOP 23
   STEP  1
      【入力】arr =           4           3           1           2
      k  =  3
   STEP  2
      l  =  4
   STEP  3
      【入れ替え】3 桁目と4 桁目
       arr =           4           3           1           2
       arr =           4           3           2           1
   STEP  4
      【逆順並び替え】4 桁目から4 桁目まで
       arr =           4           3           2           1
       arr =           4           3           2           1
      【出力：】arr =           4           3           2           1
LOOP 24
```
</details>

....ということでarr(4)=(1,2,3,4)の順列を順番に２３個求めてみました。
組み合わせの数は 4!=24なので、一番初めの順列(1,2,3,4)を含めると２４個となります。

## プログラム例
先ほどの計算例をFortranで実装した結果が以下の通りとなります。
プログラムでは、subroutine next_permutationで次の順列を求めています。

```fortran
program test_next_permutation
    implicit none
    integer i, n
    integer, allocatable :: arr(:)

    !対象配列
    allocate (arr(4))
    arr = (/1, 2, 3, 4/)
    n = 4

    !組み合わせ検索
    call next_permutation(arr, n)

end program

subroutine next_permutation(arr, n)
    integer n, k, kari, arr(4), tmp(4), i, j
    j = 1
    do
        write (*, '(a,i2)') 'LOOP ', j
        !STEP 1
        do k = n - 1, 1, -1
            if (arr(k) < arr(k + 1)) exit
            if (k == 1) stop !STEP1が成立しない場合は終了です。
        end do
        write (*, *) '  STEP  1'
        write (*, *) '     【入力】arr =', arr
        write (*, '(a, i0)') '      k  =  ', k

        !STEP 2
        write (*, *) '  STEP  2'
        do l = n, k + 1, -1
            if (arr(k) < arr(l)) exit
        end do
        write (*, '(a, i0)') '      l  =  ', l

        !STEP 3
        write (*, *) '  STEP  3'
        write (*, '(a,i0,a, i0,a)') '      【入れ替え】', k, ' 桁目と', l, ' 桁目'
        write (*, *) '      arr =', arr
        kari = arr(k)
        arr(k) = arr(l)
        arr(l) = kari
        write (*, *) '      arr =', arr

        !STEP 4
        write (*, *) '  STEP  4'
        write (*, '(a,i0,a, i0,a)') '      【逆順並び替え】', k + 1, ' 桁目から', n, ' 桁目まで'
        write (*, *) '      arr =', arr
        if (k + 1 /= n) then
            do i = 1, k
                tmp(i) = arr(i)
            end do
            do i = 0, n - (k + 1)
                tmp(n - i) = arr(k + 1 + i)
            end do
            arr = tmp
        end if
        write (*, *) '      arr =', arr
        write (*, *) '     【出力：】arr =', arr
        j = j + 1
    end do

end subroutine
```