← voltar para a publicação›Editar / bifurcar

number of partitions of some k

#7N9dkqduftpublic / publicnova versão

anônimo criado 7 days ago Expira em 7 hours 1.8 KB sintaxe: rust

Suas alterações criam uma nova publicação vinculada a esta — a original não é alterada.

nova versão Suas alterações criam uma nova publicação vinculada a esta — a original não é alterada.

Visibilidade Feed público Acesso public

Nota da alteração (opcional)

Esta publicação aparecerá no feed público. Altere Visibilidade se quiser compartilhar apenas por link.

Cancelar

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());
    }
}