algorithm - 如何将集合的元素分组为N个部分的所有组合？

Question

我遇到了一个看起来很简单但实际上却很困难的问题。它似乎是组合算法的子集。有更快，更直接的算法吗？

/// split the group {v1} to {n} parts
///
/// For example:
///  Group(here represented by an array):
///   [1, 2, 3, 4]
///  split Group to 2 part, got:
///   [[1], [2, 3, 4]]
///   [[1, 2], [3, 4]]
///   [[1, 3], [2, 4]]
///   [[1, 4], [2, 3]]
///   [[1, 2, 3], [4]]
fn split_group(v1: Vec<i32>, n: i32) -> Vec<Vec<Vec<i32>>> {
    unimplemented!()
}

fn main() {
    let mut v1 = vec![1, 2, 3, 4];
    let v2 = split_group(v1, 2);
    assert_eq!(
        v2,
        vec![
            vec![vec![1], vec![2, 3, 4]],
            vec![vec![1, 2], vec![3, 4]],
            vec![vec![1, 3], vec![2, 4]],
            vec![vec![1, 4], vec![2, 3]],
            vec![vec![1, 2, 3], vec![4]],
        ]
    );
}

Answer 1

这是从@MBo链接的this answer派生的解决方案。
递归函数用N个值填充K个零件。lastfilled参数有助于避免重复-它提供了每个部分中前导(最小)元素的递增顺序。empty参数旨在避免出现空的部分。

use std::cmp;

pub fn genp(parts: &mut Vec<Vec<usize>>, mut empty: usize, n: usize, k: usize, m: usize, lastfilled: Option<usize>) {
    if m == n {
        return println!("{:?}", parts);
    }
    let mut start = 0;
    if n - m == empty {
        start = k - empty;
    }
    let max = match lastfilled {
        None => 1,
        Some(lastfilled) => lastfilled + 2,
    };
    for i in start..cmp::min(k, max) {
        parts[i].push(m);
        if parts[i].len() == 1 {
            empty -= 1;
        }
        genp(parts, empty, n, k, m+1, cmp::max(Some(i), lastfilled));
        parts[i].pop();
        if parts[i].is_empty() {
            empty += 1;
        }
    }
}

pub fn split_group(v1: Vec<i32>, k: usize) {
    let mut parts: Vec<Vec<usize>> = Vec::new();
    for _ in 0..k {
        parts.push(Vec::new());
    }
    genp(&mut parts, k, v1.len(), k, 0, None);
}

fn main() {
    let v1 = vec![1, 2, 3, 4];
    split_group(v1, 2);
}

[[0, 1, 2], [3]]
[[0, 1, 3], [2]]
[[0, 1], [2, 3]]
[[0, 2, 3], [1]]
[[0, 2], [1, 3]]
[[0, 3], [1, 2]]
[[0], [1, 2, 3]]