2024年5月25日

ドラマ「SUITS」日本版のとある話をみていたら、8つの金額を組み合わせのなかから合計がちょうど指定の金額になるようなものを探すというシーンがあって、「8つの組み合わせでも無限にある」と言いつつも、どうやったのか、彼らはそれを解いたことになっていた。ナップサック問題だ。

_combinations: 与えられた要素のすべての組み合わせを出力する配列関数

与えられた要素のすべての組み合わせを出力する配列関数 _combinations の概要はこんなものだ。

要素の整列 — 与えられた要素を SORT して、同じ要素が一か所に固まるようにする。
要素を添え字で — 与えられた要素を直接扱うのではなく対応する添え字（整数）の形で扱う（XMATCH）。
組み合わせを文字列で — 添え字の一組み合わせをカンマ区切りの文字列として表現する（TEXTJOIN）。
脱重複 — 組み合わせ文字列の列中の重複を取り除く（UNIQUE）。
要素に戻す — 添え字の組み合わせのカンマ区切り文字列表現を要素の配列に戻す。

肝となる組み合わせ文字列の生成部分（_indexCombinations_aux）の考え方はこんなものだ。

与えられた添え字の集合 _is を組み合わせの一つとして記録する。
さらに、_is のうち1つ目を除去した部分集合の全組み合わせを求める（部分集合での再帰）。
さらに、_is のうち2つ目を除去した部分集合の全組み合わせを求める（部分集合での再帰）。
さらに、_is のうち3つ目を除去した部分集合の全組み合わせを求める（部分集合での再帰）。
$\vdots$（以下同様）

※再帰呼び出しには不動点コンビネーター（_rec）を使っている。

=LET(
  _combinations,
    LAMBDA(_elements,[_condition],[_torow],
       LET(
         _es, SORT(TOCOL(_elements)),
         _is, XMATCH(_es, _es),

         _INDEX_SEPARATOR, ",",

         _indexCombinations,
           LET(
             _dropRowAt,
               LAMBDA(_array, _rowIndex,
                 LET(
                   _array_rows, ROWS(_array),
                   IFS(
                     _rowIndex<1, _array,
                     _rowIndex>_array_rows, _array,
                     _array_rows=1, NA(),
                     _rowIndex=1, DROP(_array,1),
                     _rowIndex=_array_rows, TAKE(_array, _array_rows-1),
                     TRUE, VSTACK(
                       TAKE(_array,_rowIndex-1),
                       DROP(_array,_rowIndex))))),

             _rec, LAMBDA(f, LET(g, LAMBDA(x, f(LAMBDA(v, LET(w, x(x), w(v))))), g(g))),

             _indexCombinations_aux,
               _rec(LAMBDA(_self,
                 LAMBDA(_is,
                   LET(
                     _is_count, ROWS(_is),
                     SWITCH(_is_count,
                       0, NA(),
                       1, _is,
                       REDUCE(
                         TEXTJOIN(_INDEX_SEPARATOR,, _is),
                         SEQUENCE(_is_count),
                         LAMBDA(_result, _cursor,
                           VSTACK(_result, _self(_dropRowAt(_is, _cursor)))))))))),

             LAMBDA(_indexes,
               UNIQUE(_indexCombinations_aux(SORT(_indexes))))),

       _condition_act,
         IF(ISOMITTED(_condition), LAMBDA(_c, TRUE), _condition),

       _torow_act,
         IF(ISOMITTED(_torow), LAMBDA(_c, _c), _torow),

       DROP(REDUCE("dummy datum",_indexCombinations(_is),
         LAMBDA(_result, _ic_expr,
           LET(_c, INDEX(_es, VALUE(TEXTSPLIT(_ic_expr, _INDEX_SEPARATOR))),
             IF(AND(_condition_act(_c)),
               VSTACK(_result, _torow_act(_c)),
               _result)))
       ), 1))),

  ～～_combinations関数を使う数式をここに書く～～
)

使用例: {"Apple", "Banana", "Orange"} のすべての組み合わせ

=LET(
  ～～上記の関数定義～～
  _combinations({"Apple","Banana","Orange"})
)

#N/A を見えなくするには IFERROR を使えばよい。

=LET(
  ～～上記の関数定義～～
  IFERROR(_combinations({"Apple","Banana","Orange"}), "")
)

使用例: {"Apple", "Banana", "Orange","Apple"} のすべての組み合わせ — 入力データに重複がある場合

=LET(
  ～～上記の関数定義～～
  _combinations({"Apple","Banana","Orange","Apple"})
)

使用例: {13,17,21,28,68,82,84,88} の組み合わせのうち、合計が200になるもの

合計値を検査する LAMBDA 関数を第2引数 _condition として与える。

=LET(
  ～～上記の関数定義～～
  _combinations({13,17,21,28,68,82,84,88}, LAMBDA(_c, SUM(_c)=200))
)

使用例: {13,17,21,28,68,82,84,88} の組み合わせのうち合計値が50～100の範囲のものと、その合計値

合計値を検査する LAMBDA 関数を第2引数 _condition として与え、合計値を計算して結果行を HSTACK で生成する LAMBDA 関数を第3引数 _torow として与える。合計値は一番左の列（図ではA列）で、それより右の列が組み合わせの内容である。

=LET(
  ～～上記の関数定義～～
  _combinations({13,17,21,28,68,82,84,88},
    LAMBDA(_c, LET(_sum,SUM(_c), AND(50<=_sum, _sum<=100))),
    LAMBDA(_c, HSTACK(SUM(_c), _c)))
)

第3引数 _torow を与える関数の出力は「行」配列でなくてもよい。

=LET(
  ～～上記の関数定義～～
  _combinations({13,17,21,28,68,82,84,88},
    LAMBDA(_c, LET(_sum,SUM(_c), AND(50<=_sum, _sum<=100))),
    LAMBDA(_c, SUM(_c) & " ＝ " & TEXTJOIN(" ＋ ",,_c)))
)

この関数は8つの要素に対して本当に255通り生成できているのか

「SUITS」で解いていた問題は8つの金額の組み合わせ問題だが、その組み合わせの個数は全部で255通りだ。

$$
{}_8C_1+{}_8C_2+{}_8C_3+{}_8C_4+{}_8C_5+{}_8C_6+{}_8C_7+{}_8C_8=255
$$

_combinations 関数は8つの要素に対して本当に255通り生成できているのか、確かめてみた。

=LET(
  ～～上記の関数定義～～
  SUM(_combinations(SEQUENCE(8),,LAMBDA(_c, 1)))
)