REDUCE関数(Excel)の使い方覚書

次の式はは$0$を初期値として$1,2,3,4,5$を順に足す計算をしています．

      =REDUCE(0, {1, 2, 3, 4, 5}, LAMBDA(a, b, a + b))
--> 15
    

また，「array」には任意の数式を入れることができ，縦配列にも対応しています．次の式はどちらも，$0$を初期値として$1,2,3,4,5$を順に足す計算をしています．

      =REDUCE(0, {1; 2; 3; 4; 5}, LAMBDA(a, b, a + b))
--> 15

=REDUCE(0, SEQUENCE(5), LAMBDA(a, b, a + b))
--> 15
    

REDUCE関数の第$2$引数は「array」としていますが，配列の要素が$1$つしかないばあいにはこういう書き方もできます．

      =REDUCE(3, 2, LAMBDA(a, b, a + b))
--> 5
    

そして「アキュムレータ」と「値」として指定する変数名には，ワイルドカード文字と演算子を除く任意の文字列が使用可能です．

      =REDUCE(0, SEQUENCE(5), LAMBDA(あ, いう, あ + いう))
--> 15
    

次の式は$6$の正の約数を横に並べる数式です．

      =REDUCE(1, SEQUENCE(5, , 2), LAMBDA(a, b, IF(MOD(6, b), a, HSTACK(a, b))))
--> {1, 2, 3, 6}
    

一気に複雑になりましたね．処理を順に追ってみましょう．
$1$回目の処理ではまず，a に 1 が代入され，b に 2 が代入されて計算が行われます．MOD(6, 2) の戻り値は 0 ですから，HSTACK(1, 2) が計算され，その戻り値である {1, 2} が a に代入されます．
$2$回目の処理では，b に 3 が代入され，MOD(6, 3) の戻り値は 0 なので HSTACK({1, 2}, 3) の戻り値である {1, 2, 3} が a に代入されます．
$3$回目の処理では，b に 4 が代入され，MOD(6, 4) の戻り値は 2 ですから，a の値である {1, 2, 3} が a に代入されます．
これを続けることで処理終了時に a には {1, 2, 3, 6} が代入された状態になり，戻り値は {1, 2, 3, 6} となるのです．

      =REDUCE(0, SEQUENCE(6), LAMBDA(a, b, IF(MOD(6, b), a, a + b)))
--> 12
    

考え方は例2のものと同じです．

漸化式
$$ a_{n + 1} = 3a_n + 1, \ \ a_1 = 1 $$
によって定まる数列をREDUCE関数で計算してみましょう．$\color{red}{\bigodot}$

      =REDUCE(1, SEQUENCE(5), LAMBDA(a, b, 3 * a + 1))
--> 364
    

これは数列の第$6$項目を計算しています．今までは「値」が計算に直接関わっていましたが，今回はカウンタとして使われていますね．
もし数列を文字通り列として取得したいなら，少し工夫が必要です．

      =REDUCE(1, SEQUENCE(5), LAMBDA(a, b, HSTACK(a, 3 * TAKE(a, , -1) + 1)))
--> {1, 4, 13, 40, 121, 364}
    

TAKE関数で次の項の計算に必要な部分を取り出しています．

漸化式
$$ a_{n + 1} = a_n + n^2, \ \ a_1 = 1 $$
によって定まる数列をREDUCE関数で計算してみましょう．

      =REDUCE(1, SEQUENCE(5), LAMBDA(a, b, a + b^2))
--> 56
    

これは数列の第$6$項目を計算しています．今回はカウンタである「値」が計算に関わっていますね．
第$6$項目までを横に並べたいなら，例4と同じようにすればよいでしょう．

      =REDUCE(1, SEQUENCE(5), LAMBDA(a, b, HSTACK(a, TAKE(a, , -1) + b^2)))
--> {1, 2, 6, 15, 31, 56}
    

$2$以上の自然数$p, n$が与えられたときに，$n$が$p$で何回割り切れるのかをREDUCE関数で計算してみましょう．$\color{red}{\bigodot}$

      =CHOOSEROWS(REDUCE(VSTACK(0, n), SEQUENCE(LOG(n, p) + 1), 
    LAMBDA(a, b, 
        IF(MOD(CHOOSEROWS(a, 2), p), 
            a, 
            a / VSTACK(1, p) + VSTACK(1, 0)
        )
    )
 ), 1)
    

少し複雑になってしまいましたね．順に説明します．
まず「array」の部分では$1$から$\log_pn + 1$までの自然数を指定しています．$1$を足しているのは，$\log_pn$が$1$未満になったときのエラー回避のためです．
そして肝心のアキュムレータの部分ですが，これは {割った回数; 残っている数} を保持するようにしています．はじめは {0; n} ですが，$2$行目が$p$で割り切れると判定されると，$2$行目を$p$で割り，$1$行目に$1$を加えます．

漸化式
$$ S_{n + 1} = \sum_{k = 1}^n (n - k + 1)S_k, \ \ S_1 = 1 $$
によって定まる数列をREDUCE関数で計算してみましょう．考え方は例4と同じです．
以下は最初の$6$項を計算しています．

      =REDUCE(1, SEQUENCE(5), LAMBDA(a, b, HSTACK(a, SUM(SEQUENCE(, b, b, -1) * a))))
--> {1, 1, 3, 8, 21, 55}
    

漸化式
$$ a_n = a_{n - 1} + 2a_{n - 2}, \ \ a_0 = 1, a_1 = 1 $$
によって定まる数列をREDUCE関数で計算してみましょう．新しい項の計算には直前の$2$項が必要なので，この$2$つだけをアキュムレータに保持しておけば良さそうです．
以下は第$n$項目を計算する式です．繰り返し回数に注意しましょう．

      =LAMBDA(n, IF(n <= 1, 1, 
    CHOOSEROWS(REDUCE(VSTACK(1, 1), SEQUENCE(n - 1), 
        LAMBDA(a, b, VSTACK(CHOOSEROWS(a, 2), SUM(VSTACK(2, 1) * a))
        )
    ), 2)
 ))
    

あるいは行列演算を利用してこのようにしても良いでしょう．

      =LAMBDA(n, IF(n <= 1, 1, 
    CHOOSEROWS(REDUCE(VSTACK(1, 1), SEQUENCE(n - 1), 
        LAMBDA(a, b, MMULT(VSTACK(HSTACK(0, 1), HSTACK(2, 1)), a)
        )
    ), 2)
 ))
    

漸化式
$$ C_{n, r} = C_{n - 1, r - 1} + C_{n - 1, r}, \ \ C_{n, 0} = C_{n, n} = 1 \ \ (\forall n) $$
によって定まる数列をREDUCE関数で計算してみましょう．これはREDUCE関数を使った漸化式の計算に慣れていないと難しいです．

まずは計算の方針を立てましょう．漸化式から，$C_{n, r}$を求めるには$C_{n - 1, r - 1}, C_{n - 1, r}$の値を知っておかなければなりません．では$C_{n - 1, r - 1}, C_{n - 1, r}$を求めるには？ と考えていくと，アキュムレータに保持するテーブルは次のような構造にすれば良いとわかるでしょう．

こんなふうに書いていますが，実際には横$1$列に引き伸ばした配列で考えます．最右端に追加する項はというと，上の表と漸化式から，$1$つ左の要素と$r+1$つ左の要素から計算されます．初期値は EXPAND(1, , r + 1, 1) として，繰り返し回数は$(r + 1)(n - r)$としましょう．よって，はじめに$n = r$か否かの場合分けをします．配列ができあがったら，最後に最右端を取り出します．

      =LAMBDA(n, r, IF(n = r, 1, 
    CHOOSECOLS(
        REDUCE(EXPAND(1, , r + 1, 1), SEQUENCE((r + 1) * (n - r), , 0), 
            LAMBDA(a, b, IF(MOD(b, r + 1) = 0, 
                HSTACK(a, 1), 
                HSTACK(a, SUM(CHOOSECOLS(a, -1, -r-1)))
            ))
        ), 
    -1)
 ))
    

漸化式
$$ S^2_{n, r} = S^2_{n - 1, r - 1} + rS^2_{n - 1, r}, \ \ S^2_{n, 0} = 0, \ \ S^2_{n, n} = 1, \ \ S^2_{0, 0} = 1 \ \ (\forall n) $$
によって定まる数列をREDUCE関数で計算してみましょう．考え方は例9のものと変わりません．

      =LAMBDA(n,r, IF(n = r, 1,
    CHOOSECOLS(REDUCE(EXPAND(1, , r + 1, 1), SEQUENCE((r + 1) * (n - r), , 0),
        LAMBDA(a,b, IF(MOD(b, r + 1) = 0,
            HSTACK(a, 0),
            HSTACK(
                a, 
                SUM(HSTACK(1, MOD(b, r + 1)) * CHOOSECOLS(a, -1, -r-1))
            )
        ))
    ), -1)
 ))
    

例9の計算では，新しい値が最右端に出てくるのに対し，配列の左側は早いうちに計算とは関係の無い余分なものとなってしまいます．実際，計算に本当に必要なのは例9の表のうち，次の$2$行だけです．

このアイデアで実装を考えていく場合，$1$行目の配列を参考に$2$行目の配列を作り，それを新しい$1$行目の配列として更新していくことになります．しかし，このような配列の要素の追加に対してはExcelはサポートしてくれていません(一応やってやれないことはないですがここでは割愛します)．そこで，$1$行目のみをアキュムレータに保持しておき，REDUCE関数の再帰処理によって作った$2$行目をアキュムレータに代入するのです．
具体的にはこうします．

      =LAMBDA(n, r, IF(n = r, 1, IF(r = 0, 1, 
    CHOOSECOLS(REDUCE(EXPAND(1, , r + 1, 1), SEQUENCE(n - r), 
        LAMBDA(a, b, 
            REDUCE(1, SEQUENCE(r), 
                LAMBDA(c, d, 
                    HSTACK(c, CHOOSECOLS(c, d) + CHOOSECOLS(a, d + 1))
                )
            )
        )
    ), -1)
 )))
    

ここでもやはり，繰り返し回数に注意します．また，戻り値がどの変数に代入されるのかを意識して組むと良いでしょう．

$n \times 3$の配列が与えられ，「与えられた配列の各行に対して，その$3$つの数値のうち，偶数が奇数より多いなら$4$列目として$0$を加え，そうでないなら$4$列目として$1$を加える」という操作をREDUCE関数で実現してみましょう．
これはまさに，「どうしても『値』に配列を代入したい」というときです．ところが実際には「値」に配列を代入させることはできません．そこで，「値」に配列の行数を代入させることで，間接的に配列の各行を取得します．

      =LAMBDA(array, DROP(REDUCE(0, SEQUENCE(ROWS(array)), 
    LAMBDA(a, b, 
        VSTACK(a, HSTACK(CHOOSEROWS(array, b), 
            CHOOSEROWS(REDUCE(VSTACK(0, 0), CHOOSEROWS(array, b), 
                LAMBDA(c, d, IF(CHOOSEROWS(c, 2) = 2, 
                    1, 
                    IF(CHOOSEROWS(c, 1) = 2, 0, IF(MOD(d, 2), 
                        c + VSTACK(0, 1), 
                        c + VSTACK(1, 0)
                    ))
                ))
            ), 1)
        ))
    )
 ), 1))
    

漸化式
$$ S^1_{n, r} = S^1_{n - 1, r - 1} + (n - 1)S^1_{n - 1, r}, \ \ S^1_{n, 0} = 0, \ \ S^1_{n, n} = 1, \ \ S^1_{0, 0} = 1 \ \ (\forall n) $$
によって定まる数列をREDUCE関数をネストして計算してみましょう．考え方は例11と同様です．

      =LAMBDA(n, r, IF(n = r, 1, IF(r = 0, 0, 
    CHOOSECOLS(REDUCE(EXPAND(1, , r + 1, 1), SEQUENCE(n - r), 
        LAMBDA(a, b, REDUCE(0, SEQUENCE(r), 
            LAMBDA(c, d, 
                HSTACK(c, CHOOSECOLS(c, -1) + (b + d - 1) * CHOOSECOLS(a, d + 1))
            )
        ))
    ), -1)
 )))
    

これを例10と同様に表を横に引き伸ばして計算しようとすると，途端に難しくなることがわかるでしょうか．

正の整数$n$が与えられるので，$n$枚ハノイの塔の最短移動手順を示す配列を，REDUCE関数で計算してみましょう．

まず考えることは戻り値をどうするかです．今回は次のようにします($n = 2$のとき)．

次に漸化式をどうするか考えます．すなわち，上の例では$n = 2$の表から$n = 3$の表を作るにはどういう操作が必要かを考えます．列の並べ替えで最短手順が本質的に不変であることを利用すれば良さそうですね．

      =LAMBDA(n, LET(ini, VSTACK(HSTACK(0, 1, 0), HSTACK(0, 0, 1)), 
    IF(n = 1, ini, 
        REDUCE(ini, SEQUENCE(n - 1), 
            LAMBDA(a, b, 
                VSTACK(a --(MOD(SEQUENCE(ROWS(a), 3), 3) = 2), 
                        IF(MOD(b, 2), 
                            CHOOSECOLS(a, 3, 1, 2) --(MOD(SEQUENCE(ROWS(a), 3), 3) = 1), 
                            CHOOSECOLS(a, 2, 3, 1) --(MOD(SEQUENCE(ROWS(a), 3), 3) = 0)
                        )
                )
            )
        )
    )
 ))
    

数論的関数$f$と正の整数$n$が与えられるので，$\displaystyle g(m) := \sum_{d\vert m, 0 < d} f(d) \ \ (\forall m)$によって定まる関数$g$に対して，$g(1), \cdots, g(n)$を列挙する数式をREDUCE関数で組んでみましょう．
ここで，$\displaystyle \sum_{d\vert m, 0 < d}$は$m$の正の約数をわたる和を表します．
あらかじめ$f(1), \cdots, f(n)$の値を用意しておくことで，計算量を少しでも減らしておきます．

      =LAMBDA(func, n, DROP(
    REDUCE(DROP(REDUCE(0, SEQUENCE(n), LAMBDA(a, b, HSTACK(a, func(b)))), , 1), 
        SEQUENCE(n), 
        LAMBDA(a, b, 
            HSTACK(a, SUM(CHOOSECOLS(a, 
                    REDUCE(, SEQUENCE(b), LAMBDA(c, d, IF(MOD(b, d), c, HSTACK(c, d))))
            )))
        )
    ), , n)
 )
    

あるいは，$f(1), \cdots, f(n)$の値を処理の外部に保存する方法もあります．

      =LAMBDA(func, n, LET(
    list, DROP(REDUCE(0, SEQUENCE(n), LAMBDA(a, b, HSTACK(a, func(b)))), , 1), 
    DROP(REDUCE(0, SEQUENCE(n), 
        LAMBDA(a, b, HSTACK(a, 
            SUM(CHOOSECOLS(list, REDUCE(, SEQUENCE(b), LAMBDA(c, d, IF(MOD(b, d), c, HSTACK(c, d))))))
        ))
    ), , 1)
 ))
    

正の整数$n, r$が与えられるので，$n$個の中から$r$個選ぶすべての組み合わせをREDUCE関数で計算してみましょう．
組み合わせがいくつあるか，ではありません．組み合わせそのものにどのようなものがあるのか，を計算するのです．今回は戻り値は次のようにします($n = 4, r = 2$のとき)．

肝心の実装方法ですが，いくつかあるものの，どれも難しいので$1$つ紹介するだけにとどめておきます．
以下はその式です．計算方法自体はパスカルの三角形を利用するものになりますが，Excelは多次元配列や辞書型を扱えませんので，例9のような表のインデックスをラベルとして付しておいて後で取り出せるようにしています．

      =LAMBDA(n, r, IF(n <= r, EXPAND(1, , n, 1), 
    LET(label, LAMBDA(array, number_1, number_2, HSTACK(TAKE(array, , n), HSTACK(number_1, number_2) * EXPAND(1, ROWS(array), , 1))), 
        add, LAMBDA(array, number, array --(MOD(SEQUENCE(ROWS(array), n + 2), n + 2) = n - number)), 
        ini, REDUCE(EXPAND(0, , n + 2, 0), SEQUENCE(r), LAMBDA(a, b, VSTACK(a, HSTACK(EXPAND(EXPAND(0, , n - b, 0), , n, 1), 0, b)))), 
        REDUCE(
            REDUCE(ini, SEQUENCE(n - r), LAMBDA(a, b, 
                REDUCE(
                    REDUCE(a, SEQUENCE(r), LAMBDA(a, c, 
                        VSTACK(a, label(VSTACK(
                                        add(FILTER(a, (CHOOSECOLS(a, -2) = IF(c = 1, 0, b)) * (CHOOSECOLS(a, -1) = c - 1)), b + c - 1), 
                                        FILTER(a, (CHOOSECOLS(a, -2) = b - 1) * (CHOOSECOLS(a, -1) = c))
                            ), b, c)
                        )
                    )), 
                    1, LAMBDA(array, c, FILTER(array, (CHOOSECOLS(array, -2) >= b - 1) + (CHOOSECOLS(array, -2) = 0)))
                )
            )), 
            1, LAMBDA(array, b, 
                TAKE(FILTER(array, (CHOOSECOLS(array, -2) = n - r) * (CHOOSECOLS(array, -1) = r)), , n)
        ))
    )
 ))
    

実はこの数式に少し手を加えることによって，labelやFILTER関数を使わずにより速い処理をすることができるのですが，さらに複雑になってしまうのでここでは触れず，勇気ある読者への課題とします．