Delete some bits and count

Question

Consider all 2^n different binary strings of length n and assume n > 2. You are allowed to delete exactly b < n/2 bits from each of the binary strings, leaving strings of length n-b remaining. The number of distinct strings remaining depends on which bits you delete. Assuming your aim is to leave as few remaining different strings as possible, this challenge is to write code to compute how few can you leave as a function of n.

Example, n=3 and b = 1. You can leave only the two strings 11 and 00.

For n=9 and b = 1,2,3,4 we have 70,18,6,2

For n=8 and b = 1,2,3 we have 40,10,4

For n=7 and b = 1,2,3 we have 20,6,2

For n=6 and b = 1,2 we have 12,4

For n=5 and b = 1,2 we have 6,2

This question was originally posed by me in 2014 in a different form on MO.

Input and output

Your code should take in an integern and output a single integer for each value of b starting at b = 0 and increasing.

Score

Your score is the largest n for which your code completes for all b < n/2 in under a minute on my Linux based PC. In case of tie breaks, the largest b your code gets to for the joint largest n wins. In case of tie breaks on that criterion too, the fastest code for the largest values of n and b decides. If the times are within a second or two of each other, the first posted answer wins.

Languages and libraries

You can use any language of library you like. Because I have to run your code, it would help if it was free (as in beer) and worked in Linux.

Answer 1

Python 2.7 / Gurobi n=9

This solution is very straight usage of Gurobi's ILP solver for the boolean Mixed-Integer Problems (MIP).

The only trick is to take out symmetry in 1's complement to halve the problem sizes.

Using Gurobi LLC's limited time "free" licence we are restricted to 2000 constraints, but solving 10 del 1 is well outside the 60 second time-limit anyway on my laptop.

from gurobipy import *
from itertools import combinations

def mincover(n,d):
    bs = pow(2,n-1-d)
    m = Model()
    m.Params.outputFlag = 0
    b = {}
    for i in range(bs):
      b[i] = m.addVar(vtype=GRB.BINARY, name="b%d" % i)
    m.update()
    for row in range(pow(2,n-1)):
      x = {}
      for i in combinations(range(n), n-d):
        v = 0
        for j in range(n-d):
          if row & pow(2,i[j]):
            v += pow(2,j)
        if v >= bs:
          v = 2*bs-1-v
        x[v] = 1
      m.addConstr(quicksum(b[i] for i in x.keys()) >= 1)
    m.setObjective(quicksum(b[i] for i in range(bs) ), GRB.MINIMIZE)
    m.optimize()
    return int(round(2*m.objVal,0))

for n in range(4,10):
    for d in range((n//2)+1):
        print n, d, mincover(n,d)

UPDATE+CORR: 10,2 has optimal solution size 31 (see e.g.) Gurobi shows no symmetric solution of size 30 exists (returns problem infeasible) .. [my attempt to show asymmetric feasibility at 30 remained inconclusive after 9.5hrs runtime] e.g. bit patterns of integers 0 7 13 14 25 28 35 36 49 56 63 64 95 106 118 128 147 159 170 182 195 196 200 207 225 231 240 243 249 252 255 or 0 7 13 14 19 25 28 35 36 49 56 63 64 95 106 118 128 159 170 182 195 196 200 207 225 231 240 243 249 252 255

Answer 2

C++, n=6

Brute force with some small optimizations.

#include<cassert>
#include<iostream>
#include<vector>

// ===========
/** Helper struct to print binary representation.
`std::cout<<bin(str,len)` prints (str:len) == the bitstring 
represented by last (len) bits of (str).
*/
struct bin{
    int str,len;
    bin(int str,int len):str(str),len(len){}
};
std::ostream& operator<<(std::ostream& str,bin a){
    if(a.len)
        return str<<bin(a.str>>1,a.len-1)<<char('0'+(a.str&1));
    else if(a.str)
        return str<<"...";
    else
        return str;
}
// ===========

/// A patten of (len) bits of ones.
int constexpr pat1(int len){
    return (1<<len)-1;
}

// TODO benchmark: make (res) global variable?

/**Append all distinct (subseqs+(sfx:sfxlen)) of (str:len) 
with length (sublen) to (res).
*/
void subseqs_(
    int str,int len,int sublen,
    int sfx,int sfxlen,
    std::vector<int>& res
){
    // std::cout<<"subseqs_ : str = "<<bin(str,len)<<", "
    // "sublen = "<<sublen<<", sfx = "<<bin(sfx,sfxlen)<<'\n';

    assert(len>=0);

    if(sublen==0){ // todo remove some branches can improve perf?
        res.push_back(sfx);
        return;
    }else if(sublen==len){
        res.push_back(str<<sfxlen|sfx);
        return;
    }else if(sublen>len){
        return;
    }

    if(str==0){
        res.push_back(sfx);
        return;
    }

    int nTrail0=0;
    for(int ncut;str&&nTrail0<sublen;

        ++nTrail0,
        ncut=__builtin_ctz(~str)+1, // cut away a bit'0' of str
        // plus some '1' bits
        str>>=ncut,
        len-=ncut
    ){
        ncut=__builtin_ctz(str)+1; // cut away a bit'1' of str
        subseqs_(str>>ncut,len-ncut,sublen-nTrail0-1,
            sfx|1<<(sfxlen+nTrail0),sfxlen+nTrail0+1,
            res
        ); // (sublen+sfxlen) is const. TODO global var?
    }

    if(nTrail0+len>=sublen) // this cannot happen if len<0
        res.push_back(sfx);
}

std::vector<int> subseqs(int str,int len,int sublen){
    assert(sublen<=len);
    std::vector<int> res;
    if(__builtin_popcount(str)*2>len){ // too many '1's, flip [todo benchmark]
        subseqs_(pat1(len)^str,len,sublen,0,0,res);
        int const p1sublen=pat1(sublen);
        for(int& r:res)r^=p1sublen;
    }else{
        subseqs_(str,len,sublen,0,0,res);
    }
    return res;
}

// ==========

/** Append all distinct (supersequences+(sfx:sfxlen)) of (str:len)
with length (suplen) to (res).
Define (a) to be a "supersequence" of (b) iff (b) is a subsequence of (a).
*/
void supseqs_(
    int str,int len,int suplen,
    int sfx,int sfxlen,
    std::vector<int>& res
){
    assert(suplen>=len);

    if(suplen==0){
        res.push_back(sfx);
        return;
    }else if(suplen==len){
        res.push_back(str<<sfxlen|sfx);
        return;
    }

    int nTrail0; // of (str)
    if(str==0){
        res.push_back(sfx);
        // it's possible that the supersequence is '0000..00'
        nTrail0=len;
    }else{
        // str != 0 -> str contains a '1' bit ->
        // supersequence cannot be '0000..00'
        nTrail0=__builtin_ctz(str);
    }
    // todo try `nTrail0=__builtin_ctz(str|1<<len)`, eliminates a branch
    // and conditional statement

    for(int nsupTrail0=0;nsupTrail0<nTrail0;++nsupTrail0){
        // (nsupTrail0+1) last bits of supersequence matches with 
        // nsupTrail0 last bits of str.
        supseqs_(str>>nsupTrail0,len-nsupTrail0,suplen-1-nsupTrail0,
            sfx|1<<(nsupTrail0+sfxlen),sfxlen+nsupTrail0+1,
            res);
    }

    int const strMatch=str?nTrail0+1:len; 
    // either '1000..00' or (in case str is '0000..00') the whole (str)

    for(int nsupTrail0=suplen+strMatch-len;nsupTrail0-->nTrail0;){
        // because (len-strMatch)<=(suplen-1-nsupTrail0),
        // (nsupTrail0<suplen+strMatch-len).

        // (nsupTrail0+1) last bits of supersequence matches with
        // (strMatch) last bits of str.
        supseqs_(str>>strMatch,len-strMatch,suplen-1-nsupTrail0,
            sfx|1<<(nsupTrail0+sfxlen),sfxlen+nsupTrail0+1,
            res);
    }

    // todo try pulling constants out of loops
}

// ==========

int n,b;
std::vector<char> done;
unsigned min_undone=0;

int result;
void backtrack(int nchoice){
    assert(!done[min_undone]);
    ++nchoice;
    std::vector<int> supers_s;
    for(int s:subseqs(min_undone,n,n-b)){
        // obviously (s) is not chosen. Try choosing (s)
        supers_s.clear();
        supseqs_(s,n-b,n,0,0,supers_s);
        for(unsigned i=0;i<supers_s.size();){
            int& x=supers_s[i];
            if(!done[x]){
                done[x]=true;
                ++i;
            }else{
                x=supers_s.back();
                supers_s.pop_back();
            }
        }

        unsigned old_min_undone=min_undone;
        while(true){
            if(min_undone==done.size()){
                // found !!!!
                result=std::min(result,nchoice);
                goto label1;
            }
            if(not done[min_undone])
                break;
            ++min_undone;
        }
        if(nchoice==result){
            // backtrack more will only give worse result
            goto label1;
        }

        // note that nchoice is already incremented
        backtrack(nchoice);

        label1: // undoes the effect of (above)
        for(int x:supers_s)
            done[x]=false;
        min_undone=old_min_undone;
    }
}

int main(){
    std::cin>>n>>b;

    done.resize(1<<n,0);
    result=1<<(n-b); // the actual result must be less than that

    backtrack(0);
    std::cout<<result<<'\n';
}

Run locally:

[user202729@archlinux golf]$ g++ -std=c++17 -O2 delbits.cpp -o delbits
[user202729@archlinux golf]$ time for i in $(seq 1 3); do ./delbits <<< "6 $i"; done
12
4
2

real    0m0.567s
user    0m0.562s
sys     0m0.003s
[user202729@archlinux golf]$ time ./delbits <<< '7 1'
^C

real    4m7.928s
user    4m7.388s
sys     0m0.173s
[user202729@archlinux golf]$ time for i in $(seq 2 3); do ./delbits <<< "7 $i"; done
6
2

real    0m0.040s
user    0m0.031s
sys     0m0.009s

Answer 3

MATLAB, n=9

Mixed-integer linear programming (MILP)

Use the intlinprog function of the optim package

% mincover.m

function result = mincover(n, d)
    bs = 2^(n - 1 - d);
    
    % define problem
    f = ones(bs, 1);
    intcon = 1:bs;
    lb = zeros(bs, 1);
    ub = ones(bs, 1);
    A = [];
    b = [];
    
    for row = 0:(2^(n-1) - 1)
        x = zeros(bs, 1);
        combs = nchoosek(1:n, n-d);
        for i = 1:size(combs, 1)
            v = 0;
            for j = 1:(n-d)
                if bitand(row, 2^(combs(i, j) - 1))
                    v = v + 2^(j - 1);
                end
            end
            if v >= bs
                v = 2*bs - 1 - v;
            end
            x(v + 1) = 1;
        end
        A = [A; x'];
        b = [b; 1];
    end
    
    options = optimoptions('intlinprog','Display','off');
    [x, fval] = intlinprog(f, intcon, -A, -b, [], [], lb, ub, options);
    result = round(2 * fval);
end

% run_mincover.m

for n = 3:9
    for d = 0:floor(n/2)
        fprintf('n=%d, d=%d, mincover=%d\n', n, d, mincover(n, d))
    end
end

n=3, d=0, mincover=8
n=3, d=1, mincover=2
n=4, d=0, mincover=16
n=4, d=1, mincover=4
n=4, d=2, mincover=2
n=5, d=0, mincover=32
n=5, d=1, mincover=6
n=5, d=2, mincover=2
n=6, d=0, mincover=64
n=6, d=1, mincover=12
n=6, d=2, mincover=4
n=6, d=3, mincover=2
n=7, d=0, mincover=128
n=7, d=1, mincover=20
n=7, d=2, mincover=6
n=7, d=3, mincover=2
n=8, d=0, mincover=256
n=8, d=1, mincover=40
n=8, d=2, mincover=10
n=8, d=3, mincover=4
n=8, d=4, mincover=2
n=9, d=0, mincover=512
n=9, d=1, mincover=70
n=9, d=2, mincover=18
n=9, d=3, mincover=6
n=9, d=4, mincover=2