← 返回文本›编辑 / 分支

number of partitions of some k

#7N9dkqduftpublic / public新版本

匿名已创建 7 days ago 过期于 7 hours 1.8 KB 语法: rust

你的更改会创建一个链接到此文本的新文本 — 原始文本不变。

新版本 你的更改会创建一个链接到此文本的新文本 — 原始文本不变。

可见性公开动态访问 public

变更备注 (可选)

此文本会显示在公开动态中。如果只想通过链接分享，请更改可见性。

取消

fn make_next(current: &[u64], i: usize, j: usize) -> Vec<u64> {
    let mut new = Vec::with_capacity(current.len()-1);
    let add = current[i]+current[j];
    //println!("{i},{j}: {}+{}={add}", current[i], current[j]);
    for k in 0..current.len() {
        let value = if k==i || k==j {0} else {current[k]};
        //println!("{k}: {value}");
        if value != 0 {
            new.push(value);
        }
    }
    let pos = new.binary_search(&add).unwrap_or_else(|e| e);
    new.insert(pos, add);
    new
}

fn get_all_next(current: &[u64]) -> Vec<Vec<u64>> {
    let mut next: Vec<Vec<u64>> = Vec::new();

for i in 0..current.len() {
        for j in i..current.len() {
            if i == j { // could maybe replace with just looping j starting from i+1 but wehh
                continue;
            }
            let check = make_next(&current, i, j);
            if !(next.contains(&check)) {
                next.push(check)
            }
        }
    }
    next
}

fn full_next(last: &[Vec<u64>]) -> Vec<Vec<u64>> {
    let mut full_next = Vec::new();

for i in last {
        let local_next = get_all_next(&i);
        for j in local_next {
            if !full_next.contains(&j) {
                full_next.push(j);
            }
        }
    }
    
    full_next
}

fn start(k: u64) -> Vec<u64> {
    vec![1u64; k as usize]
}

fn collect_all(k: u64) -> Vec<Vec<u64>> {
    let rounds = (k-2) as usize;
    let mut all = Vec::new();
    let start = start(k);
    let mut next = get_all_next(&start);
    all.push(start);
    for _ in 0..rounds {
        let mut last = next;
        next = full_next(last.as_slice());
        all.append(&mut last);
    }
    all
}

fn main() {
    for i in 2..=10 {
        let collect = collect_all(i);
        println!("{:?}\nLENGTH = {}", collect, collect.len());
    }
}