Rustで nHr の全探索（重複可の組み合わせ）

ABC165C が解けなかったので整理します

nPr, nCk, nHr といったヤツらの各組み合わせをRustで全探索する方法をまとめます

選択肢1. itertools

Rustの itertools クレートには、「順列」「組み合わせ」「重複可の組み合わせ」に対応して permutations, combinations, combinations_with_replacement というメソッドが存在します(参考: itertoolsのDocument ) 。したがって例えば以下のように 3つから2つを重複可で取り出す 6つの組み合わせが得られます:

use itertools::Itertools;
fn main() {
    (0..3).combinations_with_replacement(2).for_each(|xs| print!("{:?}",xs));
}
/* 出力: [0, 0][0, 1][0, 2][1, 1][1, 2][2, 2] */

組み合わせの数「だけ」を知りたい場合は nPr, nCr, nHr の公式から得られますが、各組み合わせにおいて何らかの計算をしたい時や、それらに対する何らかの操作（最大値を求めたり、総和を求めたり）をしたい時には上述のように具体的に一つ一つの組み合わせがどのようなものかを知る必要があり、itertools はそのための道具になります。

選択肢2. 深さ優先探索（DFS）

itertools を使わなくても、上記のような組み合わせを作るのは簡単です。3つから2つを重複可で取り出す組み合わせは2重ループで簡単に求まります:

for i in 0..3 {
   for j in i..3 {
        print!(r"[{},{}]", i,j);
   }
}
// 出力: [0,0][0,1][0,2][1,1][1,2][2,2]

しかし一般の場合ではr重ループを記述できないので再帰をつかいます:

fn main() {
    let (n, r) = (3, 2);
    let mut buf = vec![0;r];
    dfs(&mut buf, 0, 0, n);
}

// 深さd においてd番目の値を決める。lb/ubはその選択肢の下限/上限
fn dfs(buf:&mut Vec<usize>, d:usize, lb:usize, ub:usize) {
    if d == buf.len() { // 「depthがバッファ長に等しい」 = 「leafの時」
        print!("{:?}", buf);
    } else {
        for i in lb..ub {
            buf[d] = i;
            dfs(buf, d+1, i, ub);
        }        
    }
}
// 出力: [0,0][0,1][0,2][1,1][1,2][2,2]

組み合わせを保持するメモリ領域は長さrのVec 1つ分で済むことは注目に値します。

その他補足

• nHr の英語は combination with replacement となりますが、「replacement」ってどういう意味？置き換え？みたいに混乱していましたが、replacement は duplicate と読み替えてよいという感じの記述をInternetで見つけました。それなら「重複ありの組み合わせ」と直訳できるので納得です
• ABC165Cでは完全に全探索する必要があるので itertools を使った解法が最も簡潔に記述できますが、問題によっては、再帰の途中で枝刈りが可能な場合も多く再帰を使った解法を覚えておくことは必須だと思います
• DFSの方法で nPr, nCr を列挙するのは少しループ周りの変数をいじることで対応可能です。