如何将一个集合的元素分组为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 链接的派生的解决方案。

递归函数用 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]]

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

How to group the elements of a collection into all combinations of N parts?

algorithm

rust

vec