↑Programmieren in Rust

Algorithmen: Kombinatorik

Inhaltsverzeichnis

1. Kartesisches Produkt
2. Kartesische Potenz
3. Potenzmenge
4. Permutationen
5. Binomialkoeffizient

Kartesisches Produkt

Variadisch für Faktoren gleichen Datentyps

fn cartesian_product<T: Clone>(a: &[Vec<T>]) -> Vec<Vec<T>> {
    if a.is_empty() {
        vec![Vec::new()]
    } else {
        let mut acc: Vec<Vec<T>> = Vec::new();
        for x in &a[0] {
            for t in cartesian_product(&a[1..]) {
                acc.push([x.clone()].iter().cloned().chain(t).collect());
            }
        }
        acc
    }
}

fn main() {
    let p = cartesian_product(&[vec![0, 1], vec![0, 1]]);
    println!("{:?}", p);
}

Kartesische Potenz

Rekursiv

fn pow_rec(a: &mut [u32], m: u32, i: usize,
    callback: &mut dyn FnMut(&[u32])
) {
    if i == a.len() {
        callback(a);
    } else {
        for k in 0..m {
            a[i] = k;
            pow_rec(a, m, i + 1, callback);
        }
    }
}

fn cartesian_power(m: u32, n: u32) -> Vec<Vec<u32>> {
    let mut acc: Vec<Vec<u32>> = vec![];
    let a = &mut vec![0; n as usize];
    pow_rec(a, m, 0, &mut |a| {
        acc.push(Vec::from(a));
    });
    acc
}

Iterativ

// Nach Umwandlung der Rekursion in eine Iteration
fn pow(a: &mut [u32], m: u32,
    callback: &mut dyn FnMut(&[u32])
) {
    let n = a.len();
    let mut stack: Vec<u32> = Vec::with_capacity(n);
    let mut k = 0;
    let mut i = 0;
    loop {
        if i == n {
            callback(a);
        } else {
            if k<m {
                a[i] = k;
                stack.push(k);
                k = 0; i += 1;
                continue;
            }
        }
        match stack.pop() {
            Some(value) => {i -= 1; k = value + 1;}
            _ => break
        }
    }
}

fn cartesian_power(m: u32, n: u32) -> Vec<Vec<u32>> {
    let mut acc: Vec<Vec<u32>> = vec![];
    let a = &mut vec![0; n as usize];
    pow(a, m, &mut |a| {
        acc.push(Vec::from(a));
    });
    acc
}

Potenzmenge

Iterativ

fn power_set<T: Clone>(a: impl IntoIterator<Item=T>) -> Vec<Vec<T>> {
    let mut ps = vec![vec![]];
    for x in a {
        for mut s in ps.clone() {
            s.push(x.clone());
            ps.push(s);
        }
    }
    ps
}

Funktional

fn power_set<T: Clone>(a: impl IntoIterator<Item = T>) -> Vec<Vec<T>> {
    a.into_iter().fold(vec![vec![]], |mut ps, x| {
        let push_x = |mut s| {s.push(x.clone()); s};
        ps.extend(ps.clone().into_iter().map(push_x));
        ps
    })
}

Permutationen

Rekursiv

// Algorithmus von Heap
fn perm<T>(a: &mut [T], n: usize,
    callback: &mut dyn FnMut(&[T])
) {
    if n == 1 {
        callback(a);
    } else {
        perm(a, n - 1, callback);
        for i in 0..n-1 {
            if n%2 == 0 {
                a.swap(i, n - 1);
            } else {
                a.swap(0, n - 1);
            }
            perm(a, n - 1, callback);
        }
    }
}

fn permutations<T: Clone>(a: &[T]) -> Vec<Vec<T>> {
    let mut acc: Vec<Vec<T>> = vec![];
    let n = a.len();
    let a = &mut Vec::from(a);
    perm(a, n, &mut |a| {acc.push(Vec::from(a));});
    acc
}

fn main() {
    println!("{:?}", permutations(&[1, 2, 3]));
}

Iterativ

// Algorithmus von Heap in der iterativen Formulierung
fn perm<T>(a: &mut [T], callback: &mut dyn FnMut(&[T])) {
    let n = a.len();
    let mut stack = vec![0; n];
    callback(a);

    let mut i = 0;
    while i<n {
        if stack[i]<i {
            if i%2 == 0 {
                a.swap(0, i);
            } else {
                a.swap(stack[i], i);
            }
            callback(a);
            stack[i] += 1;
            i = 0;
        } else {
            stack[i] = 0;
            i += 1;
        }
    }
}

fn permutations<T: Clone>(a: &[T]) -> Vec<Vec<T>> {
    let mut acc: Vec<Vec<T>> = vec![];
    let a = &mut Vec::from(a);
    perm(a, &mut |a| {acc.push(Vec::from(a));});
    acc
}

fn main() {
    for t in permutations(&[1, 2, 3]) {
        println!("{:?}", t);
    }
}

Binomialkoeffizient

fn choose(n: u64, mut k: u64) -> u64 {
    if k > n {return 0;}
    if k > n - k {k = n - k;}
    let mut acc = 1;
    for i in 0..k {
        acc = acc*(n - i)/(i + 1);
    }
    acc
}

fn tabluate(label: &str, a0: u64, a1: u64, b0: u64, b1: u64,
    shift: usize, f: &dyn Fn(u64,u64)->u64)
{
    print!("{:^5}|", label);
    for b in b0..=b1 {print!("{:>1$}", b, shift);}
    println!("\n{:\u{2500}<1$}", "", 6 + shift*((b1 - b0 + 1) as usize));
    for a in a0..=a1 {
        print!("{:>4} |", a);
        for b in b0..=b1 {print!("{:>1$}", f(a, b), shift);}
        println!();
    }
}

fn main() {
    tabluate("n\\k", 0, 10, 0, 10, 4, &choose);
}