DP explicit

combination.rs

fn main() {
    let n = 4;
    let mut dp = vec![vec![Vec::<Vec<usize>>::new(); n + 1]; n + 1];
    dp[0][0] = vec![vec![]];
    for i in 1..=n {
        for j in 1..=n {
            let mut tmp = dp[i - 1][j].clone();

            for x in dp[i - 1][j - 1].clone() {
                tmp.push(x.into_iter().chain(Some(i - 1)).collect());
            }

            dp[i][j] = tmp;
        }
    }

    for i in 0..=n {
        println!("[{i}]:");
        for j in 0..=i {
            println!("    [{j}]:");
            for x in &dp[i][j] {
                println!("        {x:?}");
            }
        }
    }
}

// [0]:
//     [0]:
//         []
// [1]:
//     [0]:
//     [1]:
//         [0]
// [2]:
//     [0]:
//     [1]:
//         [0]
//     [2]:
//         [0, 1]
// [3]:
//     [0]:
//     [1]:
//         [0]
//     [2]:
//         [0, 1]
//         [0, 2]
//     [3]:
//         [0, 1, 2]
// [4]:
//     [0]:
//     [1]:
//         [0]
//     [2]:
//         [0, 1]
//         [0, 2]
//         [0, 3]
//     [3]:
//         [0, 1, 2]
//         [0, 1, 3]
//         [0, 2, 3]
//     [4]:
//         [0, 1, 2, 3]

excel.rs

fn main() {
    let s: Vec<_> = "XLSX".chars().collect();
    let n = s.len();

    let mut dp = vec![vec![Vec::<String>::new(); 3]; n + 1];
    let [lt, eq, gt] = [0, 1, 2];
    dp[0][eq] = vec!["".to_owned()];
    for i in 1..=n {
        let si = s[n - i];
        {
            let mut tmp = vec![];
            for c in 'A'..si {
                for t in dp[i - 1].iter().flatten() {
                    tmp.push(format!("{c}{t}"));
                }
            }
            for t in &dp[i - 1][lt] {
                tmp.push(format!("{si}{t}"));
            }
            dp[i][lt] = tmp;
        }
        {
            let mut tmp = vec![];
            for t in &dp[i - 1][eq] {
                tmp.push(format!("{si}{t}"));
            }
            dp[i][eq] = tmp;
        }
        {
            let mut tmp = vec![];
            for t in &dp[i - 1][gt] {
                tmp.push(format!("{si}{t}"));
            }
            for c in (si..='Z').skip(1) {
                for t in dp[i - 1].iter().flatten() {
                    tmp.push(format!("{c}{t}"));
                }
            }
            dp[i][gt] = tmp;
        }
    }

    for x in dp[1..n].iter().flatten().flatten().chain(&dp[n][lt]).chain(&dp[n][eq]) {
        println!("{x}");
    }
}

// A
// B
// C
// ...
// AA
// AB
// ...
// AZ
// BA
// ...
// ZZ
// AAA
// ...
// AAAA
// ....
// XLSW
// XLSX

fibonacci.rs

fn main() {
    let n = 6;
    let mut dp = vec![Vec::<Vec<u32>>::new(); n + 1];
    dp[0] = vec![vec![]];
    for i in 1..=n {
        let mut cur = vec![];
        for x in dp[i - 1].clone() {
            cur.push(Some(1).into_iter().chain(x).collect());
        }
        if i >= 2 {
            for x in dp[i - 2].clone() {
                cur.push(Some(2).into_iter().chain(x).collect());
            }
        }
        dp[i] = cur;
    }

    for i in 0..=n {
        println!("[{i}]:");
        for x in &dp[i] {
            println!("    {x:?}");
        }
    }
}

// [0]:
//     []
// [1]:
//     [1]
// [2]:
//     [1, 1]
//     [2]
// [3]:
//     [1, 1, 1]
//     [1, 2]
//     [2, 1]
// [4]:
//     [1, 1, 1, 1]
//     [1, 1, 2]
//     [1, 2, 1]
//     [2, 1, 1]
//     [2, 2]
// [5]:
//     [1, 1, 1, 1, 1]
//     [1, 1, 1, 2]
//     [1, 1, 2, 1]
//     [1, 2, 1, 1]
//     [1, 2, 2]
//     [2, 1, 1, 1]
//     [2, 1, 2]
//     [2, 2, 1]
// [6]:
//     [1, 1, 1, 1, 1, 1]
//     [1, 1, 1, 1, 2]
//     [1, 1, 1, 2, 1]
//     [1, 1, 2, 1, 1]
//     [1, 1, 2, 2]
//     [1, 2, 1, 1, 1]
//     [1, 2, 1, 2]
//     [1, 2, 2, 1]
//     [2, 1, 1, 1, 1]
//     [2, 1, 1, 2]
//     [2, 1, 2, 1]
//     [2, 2, 1, 1]
//     [2, 2, 2]

interval.rs

fn main() {
    let s = vec![(0, 3), (2, 7), (1, 5), (6, 8)];

    let len = s.iter().flat_map(|&(l, r)| [l, r]).max().unwrap();

    let s_r = {
        let mut s_r = vec![vec![]; len + 1];
        for &(l, r) in &s {
            s_r[r].push((l, r));
        }
        s_r
    };

    let mut dp =
        vec![vec![Vec::<Vec<(usize, usize)>>::new(); len + 1]; len + 1];
    dp[0][0] = vec![vec![]];

    for i in 1..=len {
        let mut cur = vec![vec![]; len + 1];

        let tmp: Vec<_> = dp[i - 1]
            .iter()
            .flatten()
            .cloned()
            .map(|v| v.into_iter().chain(s_r[i].clone()).collect())
            .collect();
        cur[i] = tmp;

        for j in 0..i {
            let mut tmp = dp[i - 1][j].clone();
            for &(l, r) in s_r[i].iter().filter(|&&(l, _)| l < j) {
                for x in &mut tmp {
                    x.push((l, r));
                }
            }
            cur[j] = tmp;
        }

        dp[i] = cur;
    }

    for i in 0..=len {
        println!("[{i}]:");
        let mut tmp = dp[len][i].clone();
        tmp.sort_unstable();
        tmp.dedup(); // (!)
        for x in tmp {
            println!("    {x:?}");
        }
    }
}

//  0  1  2  3  4  5  6  7  8
//
//  [--------)
//        [--------------)
//     [-----------)
//                    [-----)

// [0]:
//     []
// [1]:
//     [(0, 3)]
// [2]:
//     [(0, 3), (1, 5)]
// [3]:
//     [(0, 3), (1, 5), (2, 7)]
// [4]:
//     [(0, 3), (1, 5), (2, 7)]
//     [(1, 5), (2, 7)]
// [5]:
//     [(0, 3), (1, 5), (2, 7)]
//     [(1, 5), (2, 7)]
// [6]:
//     [(0, 3), (1, 5), (2, 7)]
//     [(0, 3), (2, 7)]
//     [(1, 5), (2, 7)]
//     [(2, 7)]
// [7]:
//     [(0, 3), (1, 5), (2, 7), (6, 8)]
//     [(0, 3), (2, 7), (6, 8)]
//     [(1, 5), (2, 7), (6, 8)]
//     [(2, 7), (6, 8)]
// [8]:
//     [(0, 3), (1, 5), (2, 7), (6, 8)]
//     [(0, 3), (1, 5), (6, 8)]
//     [(0, 3), (2, 7), (6, 8)]
//     [(0, 3), (6, 8)]
//     [(1, 5), (2, 7), (6, 8)]
//     [(2, 7), (6, 8)]
//     [(6, 8)]

natural-number-bwd.rs

fn main() {
    let mut a = 271;
    let n = format!("{a}").len();
    let digit = |i| a / 10_u32.pow(i as u32) % 10;

    let [less, eq, gtr] = [0, 1, 2];
    let mut dp = vec![vec![Vec::<u32>::new(); 3]; n + 1];
    dp[0][eq] = vec![0];

    for i in 1..=n {
        let deq = digit(i - 1);

        let ten = 10_u32.pow(i as u32 - 1);
        {
            let mut tmp = vec![];
            for d in 0..deq {
                for &lo in dp[i - 1].iter().flatten() {
                    tmp.push(ten * d + lo);
                }
            }
            for &lo in &dp[i - 1][less] {
                tmp.push(ten * deq + lo);
            }
            dp[i][less] = tmp;
        }
        {
            let mut tmp = vec![];
            for &lo in &dp[i - 1][eq] {
                tmp.push(ten * deq + lo);
            }
            dp[i][eq] = tmp;
        }
        {
            let mut tmp = vec![];
            for &lo in &dp[i - 1][gtr] {
                tmp.push(ten * deq + lo);
            }
            for d in deq + 1..=9 {
                for &lo in dp[i - 1].iter().flatten() {
                    tmp.push(ten * d + lo);
                }
            }
            dp[i][gtr] = tmp;
        }
    }

    for i in 0..=n {
        println!("[{i}]:");
        println!("    [<]:");
        println!("        {:?}", dp[i][less]);
        println!("    [=]:");
        println!("        {:?}", dp[i][eq]);
        println!("    [>]:");
        println!("        {:?}", dp[i][gtr]);
    }
}

// [0]:
//     [<]:
//         []
//     [=]:
//         [0]
//     [>]:
//         []
// [1]:
//     [<]:
//         [0]
//     [=]:
//         [1]
//     [>]:
//         [2, 3, 4, 5, 6, 7, 8, 9]
// [2]:
//     [<]:
//         [0, 1, 2, 3, 4, /* ..., */ 69, 70]
//     [=]:
//         [71]
//     [>]:
//         [72, 73, 74, 75, 76, /* ..., */ 98, 99]
// [3]:
//     [<]:
//         [0, 1, 2, 3, 4, /* ..., */ 269, 270]
//     [=]:
//         [271]
//     [>]:
//         [272, 273, 274, 275, 276, /* ..., */ 998, 999]

natural-number-fwd.rs

fn main() {
    let mut a = 271;
    let n = format!("{a}").len();
    let digit = |i| a / 10_u32.pow((n - i) as u32) % 10;

    let mut dp = vec![vec![Vec::<u32>::new(); 2]; n + 1];
    let [loose, tight] = [0, 1];
    dp[0][tight] = vec![0];
    for i in 1..=n {
        dp[i][tight] =
            dp[i - 1][tight].iter().map(|&x| 10 * x + digit(i)).collect();

        dp[i][loose] = dp[i - 1][loose]
            .iter()
            .flat_map(|&x| (0..=9).map(move |j| 10 * x + j))
            .chain(
                dp[i - 1][tight]
                    .iter()
                    .flat_map(|&x| (0..digit(i)).map(move |j| 10 * x + j)),
            )
            .collect();
    }

    for i in 0..=n {
        println!("[{i}]:");
        println!("    [<]:");
        println!("        {:?}", dp[i][loose]);
        println!("    [=]:");
        println!("        {:?}", dp[i][tight]);
    }
}

// [0]:
//     [<]:
//         []
//     [=]:
//         [0]
// [1]:
//     [<]:
//         [0, 1]
//     [=]:
//         [2]
// [2]:
//     [<]:
//         [0, 1, 2, 3, 4, /* ..., */ 25, 26]
//     [=]:
//         [27]
// [3]:
//     [<]:
//         [0, 1, 2, 3, 4, /* ..., */ 25, 26, 27, 28, /* ..., */ 268, 269, 270]
//     [=]:
//         [271]

parentheses.rs

fn main() {
    let n = 4;

    let mut dp = vec![vec![Vec::<String>::new(); n + 1]; n + 1];
    for i in 0..n {
        dp[i][i + 1].push("a".to_owned());
    }

    for w in 2..=n {
        for l in 0..=n - w {
            let r = l + w;
            let mut tmp = vec![];
            for m in l + 1..r {
                for pl in &dp[l][m] {
                    for pr in &dp[m][r] {
                        tmp.push(format!("({pl}*{pr})"));
                    }
                }
            }
            dp[l][r] = tmp;
        }
    }

    for l in 0..n {
        for r in l + 1..=n {
            println!("[{l}..{r}]:");
            for x in &dp[l][r] {
                println!("    {x}");
            }
        }
    }
}

// [0..1]:
//     a
// [0..2]:
//     (a*a)
// [0..3]:
//     (a*(a*a))
//     ((a*a)*a)
// [0..4]:
//     (a*(a*(a*a)))
//     (a*((a*a)*a))
//     ((a*a)*(a*a))
//     ((a*(a*a))*a)
//     (((a*a)*a)*a)
// [1..2]:
//     a
// [1..3]:
//     (a*a)
// [1..4]:
//     (a*(a*a))
//     ((a*a)*a)
// [2..3]:
//     a
// [2..4]:
//     (a*a)
// [3..4]:
//     a

partition.rs

use std::collections::BTreeSet;

fn main() {
    let n = 4;
    let mut dp = vec![Vec::<Vec<usize>>::new(); 1 << n];
    let whole = !(!0 << n);

    dp[0] = vec![vec![]];

    for i in 1_usize..1 << n {
        let min = i & i.wrapping_neg();
        let wo_min = i ^ min;
        let mut tmp = vec![];
        for j in std::iter::successors(Some(wo_min), |&j| {
            (j > 0).then(|| (j - 1) & wo_min)
        }) {
            for p in dp[j].clone() {
                tmp.push(Some(i & !j).into_iter().chain(p).collect());
            }
        }
        dp[i] = tmp;
    }

    for i in 0..1 << n {
        println!("{:?}:", explicit(&[i]).iter().next().unwrap());
        for p in &dp[i] {
            println!("    {:?}", explicit(p));
        }
    }
}

fn explicit(ptn: &[usize]) -> Vec<Vec<usize>> {
    ptn.iter()
        .map(|set| (0..32).filter(|&i| set >> i & 1 != 0).collect())
        .collect()
}

// []:
//     []
// [0]:
//     [[0]]
// [1]:
//     [[1]]
// [0, 1]:
//     [[0], [1]]
//     [[0, 1]]
// [2]:
//     [[2]]
// [0, 2]:
//     [[0], [2]]
//     [[0, 2]]
// [1, 2]:
//     [[1], [2]]
//     [[1, 2]]
// [0, 1, 2]:
//     [[0], [1], [2]]
//     [[0], [1, 2]]
//     [[0, 1], [2]]
//     [[0, 2], [1]]
//     [[0, 1, 2]]
// [3]:
//     [[3]]
// [0, 3]:
//     [[0], [3]]
//     [[0, 3]]
// [1, 3]:
//     [[1], [3]]
//     [[1, 3]]
// [0, 1, 3]:
//     [[0], [1], [3]]
//     [[0], [1, 3]]
//     [[0, 1], [3]]
//     [[0, 3], [1]]
//     [[0, 1, 3]]
// [2, 3]:
//     [[2], [3]]
//     [[2, 3]]
// [0, 2, 3]:
//     [[0], [2], [3]]
//     [[0], [2, 3]]
//     [[0, 2], [3]]
//     [[0, 3], [2]]
//     [[0, 2, 3]]
// [1, 2, 3]:
//     [[1], [2], [3]]
//     [[1], [2, 3]]
//     [[1, 2], [3]]
//     [[1, 3], [2]]
//     [[1, 2, 3]]
// [0, 1, 2, 3]:
//     [[0], [1], [2], [3]]
//     [[0], [1], [2, 3]]
//     [[0], [1, 2], [3]]
//     [[0], [1, 3], [2]]
//     [[0], [1, 2, 3]]
//     [[0, 1], [2], [3]]
//     [[0, 1], [2, 3]]
//     [[0, 2], [1], [3]]
//     [[0, 2], [1, 3]]
//     [[0, 1, 2], [3]]
//     [[0, 3], [1], [2]]
//     [[0, 3], [1, 2]]
//     [[0, 1, 3], [2]]
//     [[0, 2, 3], [1]]
//     [[0, 1, 2, 3]]

permutation-exp.rs

fn main() {
    let n = 3;
    let mut dp = vec![Vec::<Vec<usize>>::new(); 1 << n];
    dp[0] = vec![vec![]];
    for i in 1..1 << n {
        let mut tmp = vec![];

        for j in (0..n).filter(|&j| i >> j & 1 != 0) {
            for t in dp[i & !(1 << j)].clone() {
                tmp.push(t.into_iter().chain(Some(j)).collect());
            }
        }

        dp[i] = tmp;
    }

    for i in 0..1 << n {
        println!("[{i}]:");
        for x in &dp[i] {
            println!("    {x:?}");
        }
    }
}

// [0]:
//     []
// [1]:
//     [0]
// [2]:
//     [1]
// [3]:
//     [1, 0]
//     [0, 1]
// [4]:
//     [2]
// [5]:
//     [2, 0]
//     [0, 2]
// [6]:
//     [2, 1]
//     [1, 2]
// [7]:
//     [2, 1, 0]
//     [1, 2, 0]
//     [2, 0, 1]
//     [0, 2, 1]
//     [1, 0, 2]
//     [0, 1, 2]

permutation-poly-1.rs

use std::collections::BTreeSet;

fn main() {
    let n = 3;

    let mut dp = vec![vec![Vec::<Vec<(usize, usize)>>::new(); n + 1]; n + 1];
    dp[0][0] = vec![vec![]];
    for i in 1..=n {
        for j in 0..=i {
            // add {}
            let mut next_dp = dp[i - 1][j].clone();

            if j >= 1 {
                for set in &dp[i - 1][j - 1] {
                    let (unused_left, unused_right) = unused(set, i - 1);

                    // add {(<i, =i)}
                    for &il in &unused_left {
                        let mut tmp = set.clone();
                        tmp.push((il, i - 1));
                        next_dp.push(tmp);
                    }

                    // add {(=i, <i)}
                    for &ir in &unused_right {
                        let mut tmp = set.clone();
                        tmp.push((i - 1, ir));
                        next_dp.push(tmp);
                    }

                    // add {(=i, =i)}
                    let mut tmp = set.clone();
                    tmp.push((i - 1, i - 1));
                    next_dp.push(tmp);
                }
            }

            if j >= 2 {
                for set in &dp[i - 1][j - 2] {
                    let (unused_left, unused_right) = unused(set, i - 1);

                    // add {(<i, =i), (=i, <i)}
                    for &il in &unused_left {
                        for &ir in &unused_right {
                            let mut tmp = set.clone();
                            tmp.push((il, i - 1));
                            tmp.push((i - 1, ir));
                            next_dp.push(tmp);
                        }
                    }
                }
            }

            dp[i][j] = next_dp;
        }
    }

    for i in 0..=n {
        println!("[{i}]:");
        for j in 0..=i {
            println!("    [{j}]:");
            for p in &dp[i][j] {
                let tmp = p.to_vec();
                println!("        {tmp:?}");
            }
        }
    }
}

fn unused(set: &[(usize, usize)], n: usize) -> (Vec<usize>, Vec<usize>) {
    let mut left: BTreeSet<_> = (0..n).collect();
    let mut right: BTreeSet<_> = (0..n).collect();
    for (l, r) in set {
        left.remove(l);
        right.remove(r);
    }
    (left.into_iter().collect(), right.into_iter().collect())
}

// [0]:
//     [0]:
//         []
// [1]:
//     [0]:
//         []
//     [1]:
//         [(0, 0)]
// [2]:
//     [0]:
//         []
//     [1]:
//         [(0, 0)]
//         [(0, 1)]
//         [(1, 0)]
//         [(1, 1)]
//     [2]:
//         [(0, 0), (1, 1)]
//         [(0, 1), (1, 0)]
// [3]:
//     [0]:
//         []
//     [1]:
//         [(0, 0)]
//         [(0, 1)]
//         [(1, 0)]
//         [(1, 1)]
//         [(0, 2)]
//         [(1, 2)]
//         [(2, 0)]
//         [(2, 1)]
//         [(2, 2)]
//     [2]:
//         [(0, 0), (1, 1)]
//         [(0, 1), (1, 0)]
//         [(0, 0), (1, 2)]
//         [(0, 0), (2, 1)]
//         [(0, 0), (2, 2)]
//         [(0, 1), (1, 2)]
//         [(0, 1), (2, 0)]
//         [(0, 1), (2, 2)]
//         [(1, 0), (0, 2)]
//         [(1, 0), (2, 1)]
//         [(1, 0), (2, 2)]
//         [(1, 1), (0, 2)]
//         [(1, 1), (2, 0)]
//         [(1, 1), (2, 2)]
//         [(0, 2), (2, 0)]
//         [(0, 2), (2, 1)]
//         [(1, 2), (2, 0)]
//         [(1, 2), (2, 1)]
//     [3]:
//         [(0, 0), (1, 1), (2, 2)]
//         [(0, 1), (1, 0), (2, 2)]
//         [(0, 0), (1, 2), (2, 1)]
//         [(0, 1), (1, 2), (2, 0)]
//         [(1, 0), (0, 2), (2, 1)]
//         [(1, 1), (0, 2), (2, 0)]

permutation-poly-2.rs

fn main() {
    let n = 3;

    {
        println!("# insert-x");
        let mut dp = vec![Vec::<Vec<usize>>::new(); n + 1];
        dp[0] = vec![vec![]];
        for i in 1..=n {
            let mut tmp = vec![];
            for p in &dp[i - 1] {
                tmp.extend(f_insert_x(p));
            }
            dp[i] = tmp;
        }
        for i in 0..=n {
            println!("[{i}]:");
            for p in &dp[i] {
                println!("    {p:?}");
            }
        }
    }
    println!();
    {
        println!("# swap");
        let mut dp = vec![Vec::<Vec<usize>>::new(); n + 1];
        dp[0] = vec![vec![]];
        for i in 1..=n {
            let mut tmp = vec![];
            for p in &dp[i - 1] {
                tmp.extend(f_swap(p));
            }
            dp[i] = tmp;
        }
        for i in 0..=n {
            println!("[{i}]:");
            for p in &dp[i] {
                println!("    {p:?}");
            }
        }
    }
    println!();
    {
        println!("# insert-y");
        let mut dp = vec![Vec::<Vec<usize>>::new(); n + 1];
        dp[0] = vec![vec![]];
        for i in 1..=n {
            let mut tmp = vec![];
            for p in &dp[i - 1] {
                tmp.extend(f_insert_y(p));
            }
            dp[i] = tmp;
        }
        for i in 0..=n {
            println!("[{i}]:");
            for p in &dp[i] {
                println!("    {p:?}");
            }
        }
    }
}

fn f_insert_x(p: &[usize]) -> impl Iterator<Item = Vec<usize>> + '_ {
    let i = p.len() + 1;
    (0..i).map(move |j| {
        let mut p = p.to_vec();
        p.insert(j, i - 1);
        p
    })
}

fn f_swap(p: &[usize]) -> impl Iterator<Item = Vec<usize>> + '_ {
    let i = p.len() + 1;
    (0..i).map(move |j| {
        let mut p = p.to_vec();
        p.push(i - 1);
        p.swap(j, i - 1);
        p
    })
}

fn f_insert_y(p: &[usize]) -> impl Iterator<Item = Vec<usize>> + '_ {
    let i = p.len() + 1;
    (0..i).map(move |j| {
        let mut p = p.to_vec();
        for pi in &mut p {
            if *pi >= j {
                *pi += 1;
            }
        }
        p.push(j);
        p
    })
}

// # insert-x
// [0]:
//     []
// [1]:
//     [0]
// [2]:
//     [1, 0]
//     [0, 1]
// [3]:
//     [2, 1, 0]
//     [1, 2, 0]
//     [1, 0, 2]
//     [2, 0, 1]
//     [0, 2, 1]
//     [0, 1, 2]
//
// # swap
// [0]:
//     []
// [1]:
//     [0]
// [2]:
//     [1, 0]
//     [0, 1]
// [3]:
//     [2, 0, 1]
//     [1, 2, 0]
//     [1, 0, 2]
//     [2, 1, 0]
//     [0, 2, 1]
//     [0, 1, 2]
//
// # insert-y
// [0]:
//     []
// [1]:
//     [0]
// [2]:
//     [1, 0]
//     [0, 1]
// [3]:
//     [2, 1, 0]
//     [2, 0, 1]
//     [1, 0, 2]
//     [1, 2, 0]
//     [0, 2, 1]
//     [0, 1, 2]

rectangle.rs

fn main() {
    let p = vec![0, 2, 5, 1, 4, 3];
    let n = p.len();
    let q = {
        let mut q = vec![0; n];
        for i in 0..n {
            q[p[i]] = i;
        }
        q
    };

    let mut dp = vec![vec![Vec::<(usize, usize)>::new(); n]; n];

    for j in q[0]..n {
        dp[0][j] = vec![(q[0], 0)];
    }

    for i in 1..n {
        for j in 0..q[i] {
            dp[i][j] = dp[i - 1][j].clone();
        }
        for j in q[i]..n {
            let mut tmp = dp[i - 1][j].clone();
            tmp.push((q[i], i));
            dp[i][j] = tmp;
        }
    }

    for i in 0..n {
        println!("[{:?}]: {:?}", (q[i], i), dp[i][q[i]]);
    }
}

// 5     *
// 4         *
// 3           *
// 2   *
// 1       *
// 0 *
//   0 1 2 3 4 5

// [(0, 0)]: [(0, 0)]
// [(3, 1)]: [(0, 0), (3, 1)]
// [(1, 2)]: [(0, 0), (1, 2)]
// [(5, 3)]: [(0, 0), (3, 1), (1, 2), (5, 3)]
// [(4, 4)]: [(0, 0), (3, 1), (1, 2), (4, 4)]
// [(2, 5)]: [(0, 0), (1, 2), (2, 5)]

stirling.rs

fn main() {
    let n = 4;

    {
        // first-kind
        println!("# cycle-permutation partition");
        let mut dp = vec![vec![Vec::<Vec<Vec<usize>>>::new(); n + 1]; n + 1];
        dp[0][0] = vec![vec![]];
        for i in 1..=n {
            for j in 1..=i {
                let mut tmp = vec![];
                for ptn in &dp[i - 1][j] {
                    for pi in 0..j {
                        for pj in 1..=ptn[pi].len() {
                            let mut ptn = ptn.to_vec();
                            ptn[pi].insert(pj, i - 1);
                            tmp.push(ptn);
                        }
                    }
                }

                for ptn in &dp[i - 1][j - 1] {
                    let mut ptn = ptn.to_vec();
                    ptn.push(vec![i - 1]);
                    tmp.push(ptn);
                }

                dp[i][j] = tmp;
                println!("{:?}:", (i, j));
                for x in &dp[i][j] {
                    println!("    {x:?}");
                }
            }
        }
    }
    println!();
    {
        // second-kind
        println!("# set partition");
        let mut dp = vec![vec![Vec::<Vec<Vec<usize>>>::new(); n + 1]; n + 1];
        dp[0][0] = vec![vec![]];
        for i in 1..=n {
            for j in 1..=i {
                let mut tmp = vec![];
                for ptn in &dp[i - 1][j] {
                    for pi in 0..j {
                        let mut ptn = ptn.to_vec();
                        ptn[pi].push(i - 1);
                        tmp.push(ptn);
                    }
                }

                for ptn in &dp[i - 1][j - 1] {
                    let mut ptn = ptn.to_vec();
                    ptn.push(vec![i - 1]);
                    tmp.push(ptn);
                }

                dp[i][j] = tmp;
                println!("{:?}:", (i, j));
                for x in &dp[i][j] {
                    println!("    {x:?}");
                }
            }
        }
    }
}

// # cycle-permutation partition
// (1, 1):
//     [[0]]
// (2, 1):
//     [[0, 1]]
// (2, 2):
//     [[0], [1]]
// (3, 1):
//     [[0, 2, 1]]
//     [[0, 1, 2]]
// (3, 2):
//     [[0, 2], [1]]
//     [[0], [1, 2]]
//     [[0, 1], [2]]
// (3, 3):
//     [[0], [1], [2]]
// (4, 1):
//     [[0, 3, 2, 1]]
//     [[0, 2, 3, 1]]
//     [[0, 2, 1, 3]]
//     [[0, 3, 1, 2]]
//     [[0, 1, 3, 2]]
//     [[0, 1, 2, 3]]
// (4, 2):
//     [[0, 3, 2], [1]]
//     [[0, 2, 3], [1]]
//     [[0, 2], [1, 3]]
//     [[0, 3], [1, 2]]
//     [[0], [1, 3, 2]]
//     [[0], [1, 2, 3]]
//     [[0, 3, 1], [2]]
//     [[0, 1, 3], [2]]
//     [[0, 1], [2, 3]]
//     [[0, 2, 1], [3]]
//     [[0, 1, 2], [3]]
// (4, 3):
//     [[0, 3], [1], [2]]
//     [[0], [1, 3], [2]]
//     [[0], [1], [2, 3]]
//     [[0, 2], [1], [3]]
//     [[0], [1, 2], [3]]
//     [[0, 1], [2], [3]]
// (4, 4):
//     [[0], [1], [2], [3]]

// # set partition
// (1, 1):
//     [[0]]
// (2, 1):
//     [[0, 1]]
// (2, 2):
//     [[0], [1]]
// (3, 1):
//     [[0, 1, 2]]
// (3, 2):
//     [[0, 2], [1]]
//     [[0], [1, 2]]
//     [[0, 1], [2]]
// (3, 3):
//     [[0], [1], [2]]
// (4, 1):
//     [[0, 1, 2, 3]]
// (4, 2):
//     [[0, 2, 3], [1]]
//     [[0, 2], [1, 3]]
//     [[0, 3], [1, 2]]
//     [[0], [1, 2, 3]]
//     [[0, 1, 3], [2]]
//     [[0, 1], [2, 3]]
//     [[0, 1, 2], [3]]
// (4, 3):
//     [[0, 3], [1], [2]]
//     [[0], [1, 3], [2]]
//     [[0], [1], [2, 3]]
//     [[0, 2], [1], [3]]
//     [[0], [1, 2], [3]]
//     [[0, 1], [2], [3]]
// (4, 4):
//     [[0], [1], [2], [3]]

subseq-1.rs

fn main() {
    let s: Vec<_> = "abaab".chars().collect();
    let n = s.len();

    let mut dp = vec![Vec::<String>::new(); n + 1];
    let mut last = vec![0, 0];
    dp[0] = vec!["".to_owned()];
    for i in 1..=n {
        let c = (s[i - 1] as u8 - b'a') as usize;
        let j = last[c];
        dp[i] = dp[j..i]
            .iter()
            .cloned()
            .flat_map(|x| x.into_iter().map(|t| format!("{}{t}", s[i - 1])))
            .collect();
        last[c] = i;
    }

    for i in 0..=n {
        println!("[{i}]:");
        for x in &dp[i] {
            println!("    {x:?}");
        }
    }
}

// [0]:
//     ""
// [1]:
//     "a"
// [2]:
//     "b"
//     "ba"
// [3]:
//     "aa"
//     "ab"
//     "aba"
// [4]:
//     "aaa"
//     "aab"
//     "aaba"
// [5]:
//     "bb"
//     "bba"
//     "baa"
//     "bab"
//     "baba"
//     "baaa"
//     "baab"
//     "baaba"

subseq-2.rs

fn main() {
    let s: Vec<_> = "abaab".chars().collect();
    let n = s.len();

    let mut dp = vec![Vec::<String>::new(); n + 1];
    dp[n] = vec!["".to_owned()];
    let mut next = vec![n, n];
    for i in (0..n).rev() {
        let mut tmp = vec![format!("{}", s[i])];

        for &j in next.iter().filter(|&&j| j < n) {
            for t in &dp[j] {
                tmp.push(format!("{}{t}", s[i]));
            }
        }

        let c = (s[i] as u8 - b'a') as usize;
        next[c] = i;
        dp[i] = tmp;
    }

    for i in 0..=n {
        println!("[{i}]:");
        for x in &dp[i] {
            println!("    {x:?}");
        }
    }
}

// [0]:
//     "a"
//     "aa"
//     "aaa"
//     "aaab"
//     "aab"
//     "ab"
//     "aba"
//     "abaa"
//     "abaab"
//     "abab"
//     "abb"
// [1]:
//     "b"
//     "ba"
//     "baa"
//     "baab"
//     "bab"
//     "bb"
// [2]:
//     "a"
//     "aa"
//     "aab"
//     "ab"
// [3]:
//     "a"
//     "ab"
// [4]:
//     "b"
// [5]:
//     ""

subset.rs

fn main() {
    let n = 4;
    let mut dp = vec![Vec::<Vec<usize>>::new(); n + 1];
    dp[0] = vec![vec![]];
    for i in 1..=n {
        let mut tmp = dp[i - 1].clone();
        for x in dp[i - 1].clone() {
            tmp.push(x.into_iter().chain(Some(i - 1)).collect());
        }
        dp[i] = tmp;
    }

    for i in 0..=n {
        println!("[{i}]:");
        for x in &dp[i] {
            println!("    {x:?}");
        }
    }
}

// [0]:
//     []
// [1]:
//     []
//     [0]
// [2]:
//     []
//     [0]
//     [1]
//     [0, 1]
// [3]:
//     []
//     [0]
//     [1]
//     [0, 1]
//     [2]
//     [0, 2]
//     [1, 2]
//     [0, 1, 2]
// [4]:
//     []
//     [0]
//     [1]
//     [0, 1]
//     [2]
//     [0, 2]
//     [1, 2]
//     [0, 1, 2]
//     [3]
//     [0, 3]
//     [1, 3]
//     [0, 1, 3]
//     [2, 3]
//     [0, 2, 3]
//     [1, 2, 3]
//     [0, 1, 2, 3]