バッチファイルでProject Euler（56）

順列を順番に出してみましょう。どういうアルゴリズムにすればよいかというと、例えば

の次は

です。まず、後ろから見ていって最初に数字が小さくなるところを探します。2のところですね。そして、また後ろから見ていって2より大きい数字を探します。それは3です。これを交換します。そして421となったのをひっくり返せばできあがりです。こうして数字が小さくなるところが見つからなくなるまで続ければ全ての順列を辞書順に出すことができます。
しかし、この方法は遅いです。10000までで90秒かかりました。

@echo off

setlocal enabledelayedexpansion
set /a N = 10000
set /a M = 10
call :range a %M%
for /L %%k in (2, 1, %N%) do (
    call :next_perm a
)
call :print_vector a
exit /b 0

:next_perm
    rem // a[k] < a[k+1]となるkを探す
    set /a k = %M% - 1
    :loop_next_perm
        if %k% == 0 exit /b 1
        set /a prev = "%1_%k%"
        set /a k -= 1
        set /a e = "%1_%k%"
        if %e% GTR %prev% goto :loop_next_perm
    
    rem // a[k] < a[l]となる最も大きいlを探す
    set /a l = %M% - 1
    set /a ak = "%1_%k%"
    :loop_next_perm2
        set /a e = "%1_%l%"
        if %ak% GTR %e% (
            set /a l -= 1
            goto :loop_next_perm2
        )
    
    rem // a[k]とa[l]を交換
    set /a tmp = "%1_%k%"
    set /a %1_%k% = "%1_%l%"
    set /a %1_%l% = %tmp%
    
    rem // a[k+1:]をひっくり返す
    set /a mid = (%k% + %M%) / 2
    set /a k_1 = %k% + 1
    for /L %%i in (%k_1%, 1, %mid%) do (
        set /a j = %M% + %k% - %%i
        set /a tmp = "%1_%%i"
        set /a %1_%%i = "%1_!j!"
        set /a %1_!j! = !tmp!
    )
    exit /b 0

:range
    set /a max_index = %2 - 1
    for /L %%k in (0, 1, %max_index%) do set /a %1_%%k = %%k
    set /a %1.size = %2
    exit /b 0

:print_vector
    setlocal
    set /a size = "%1.size"
    if %size% == 0 echo %2 & exit /b 0
    set /a e = "%1_0"
    set s=%e%
    set /a k = 1
    :loop_print_vector
        if %k% == %size% echo %s% & exit /b 0
        set /a e = "%1_%k%"
        set s=%s%%e%
        set /a k += 1
        goto :loop_print_vector