← volver a la publicación›Editar / bifurcar

number of partitions of some k

#7N9dkqduftpublic / publicnueva versión

anónimo creado 7 days ago Caduca en 7 hours 1.8 KB sintaxis: rust

Tus cambios crean una nueva publicación enlazada a esta — la original no se toca.

nueva versión Tus cambios crean una nueva publicación enlazada a esta — la original no se toca.

Visibilidad Feed público Acceso public

Nota de cambio (opcional)

Esta publicación aparecerá en el feed público. Cambia Visibilidad si solo quieres compartirla por enlace.

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