Finds the bit permutation that gives the lowest maximum

popcount.rs

use rand;

fn transpose(data: &[u64], col: usize) -> u64 {
    return data.iter().fold(0, |acc, x| (acc<<1) | ((x >> col) & 1));
}

fn masked_lowest_popcount(mask: u64, data: Vec<u64>) -> (Vec<u64>, Vec<u64>) {
    let mut lowest = u32::max_value();
    let mut values: Vec<u64> = Vec::new();
    let mut remainder: Vec<u64> = Vec::new();
    for num in data {
        let popcount = (num & mask).count_ones();
        if popcount == lowest {
            values.push(num);
        } else if popcount < lowest {
            remainder.append(&mut values);
            values.push(num);
            lowest = popcount;
        } else {
            remainder.push(num);
        }
    }
    return (values, remainder);
}

fn lowest_permutation(mask: u64, permutation: Vec<u64>, remainder: Vec<u64>) -> Vec<u64> {
    println!("mask: {}", mask);
    println!("perm: {:?}", permutation);
    println!("rem : {:?}", remainder);

    if remainder.is_empty() {
        // we're done
        return permutation;
    }
    // find the columns in the critical set that have the lowest popcount
    let (candidate_cols, remainder) = masked_lowest_popcount(mask, remainder);
    if mask.count_ones() == 1 {
        // there is only one critical row left
        // append all zeros followed by all ones
        // done
        let mut perm = permutation.clone();
        perm.extend(candidate_cols);
        perm.extend(remainder);
        return perm
    }
    // there are several rows with a 1 in the critical set
    // for the current column: recursively try them all
    let mut result = Vec::new();
    for (i, col) in candidate_cols.iter().enumerate() {
        let mut perm = permutation.clone();
        let mut rem = remainder.clone();
        perm.push(*col);
        for (j, other) in candidate_cols.iter().enumerate() {
            if i != j {
                rem.push(*other);
            }
        }
        // intersect the mask with the candidate column
        // all rows with a zero in the candidate are
        // guaranteed lower than the candidate, so uninteresting
        println!("mask: {}, col: {}", mask, col);
        let mask = if(mask & col != 0) { mask & col } else { mask };
        assert!(mask != 0);
        let candidate_result = lowest_permutation(mask, perm, rem);
        // TODO check if this is the best one
        result = candidate_result;
    }
    return result;
}

fn main() {
    let data: [u64; 8] = rand::random();
    for row in &data {
        println!("{:#066b}", row);
    }
    let mut cols: Vec<u64> = (0..64).map(|x| transpose(&data, x)).collect();
    let perm = lowest_permutation(u64::max_value(), Vec::new(), cols);
    let mut rows: Vec<u64> = (0..8).map(|x| transpose(&perm, x)).collect();
    for row in rows {
        println!("{:#066b}", row);
    }
}