Einige Bits löschen und zählen

26

Betrachten Sie alle 2^nunterschiedlichen binären Zeichenfolgen der Länge nund nehmen Sie an n > 2. Sie können genau b < n/2Bits aus jeder der binären Zeichenfolgen löschen , wobei Zeichenfolgen mit n-bverbleibender Länge übrig bleiben. Die Anzahl der verbleibenden Zeichenfolgen hängt davon ab, welche Bits Sie löschen. Angenommen, Sie möchten so wenig verschiedene Zeichenfolgen wie möglich übrig lassen, besteht diese Herausforderung darin, Code zu schreiben, um zu berechnen, wie wenig Sie als Funktion von verlassen können n.

Beispiel n=3und b = 1. Sie können nur die beiden Zeichenfolgen 11und 00.

Für n=9und b = 1,2,3,4wir haben70,18,6,2

Für n=8und b = 1,2,3wir haben40,10,4

Für n=7und b = 1,2,3wir haben20,6,2

Für n=6und b = 1,2wir haben12,4

Für n=5und b = 1,2wir haben6,2

Diese Frage wurde ursprünglich von mir 2014 in einer anderen Form zu MO gestellt .

Ein- und Ausgabe

Ihr Code sollte eine Ganzzahl aufnehmen nund eine einzelne Ganzzahl für jeden Wert ausgeben, der mit " bBeginnen bei" b = 0und "Erhöhen" beginnt .

Ergebnis

Ihre Punktzahl ist die höchste, nfür die Ihr Code b < n/2auf meinem Linux-basierten PC in weniger als einer Minute vollständig ist . Im Falle von Unentschieden wird der größte bIhrer Codes für die gemeinsamen größten nGewinne erreicht. Auch bei Unentschieden nach diesem Kriterium entscheidet der schnellste Code für die größten Werte von nund b. Wenn die Zeiten innerhalb einer oder zweier Sekunden liegen, gewinnt die erste gesendete Antwort.

Sprachen und Bibliotheken

Sie können jede Sprache der Bibliothek verwenden, die Sie mögen. Da ich Ihren Code ausführen muss, würde es helfen, wenn er kostenlos wäre (wie in Bier) und unter Linux funktioniert.

Anush
quelle
Nehme ich b > 0als zusätzlichen eingabebedarf an? Oder würde n=3und b=0einfach 2^nals Ergebnis ausgeben ?
Kevin Cruijssen
@ KevinCruijssen Es sollte in der 2^nTat ausgeben .
Anush
Sie sagen auch, dass es sich bei der Eingabe um eine einzelne nund eine einzelne Eingabe handelt. bDie Punktzahl ist jedoch die größte, nfür die der Code b < n/2in weniger als einer Minute vollständig ist . Wäre es nin diesem Fall nicht besser, eine einzige Eingabe zu haben und alle Ergebnisse für auszugeben 0 <= b < n/2? Oder sollten wir bieten zwei Programme / Funktionen: eine Aufnahme zwei Eingänge nund b, und eine einzige Eingabe nehmen nund alle Ergebnisse im Bereich ausgibt 0 <= b < n/2?
Kevin Cruijssen
2
Nun, ich hatte Ihre Herausforderung bereits positiv bewertet, kann sie also nicht noch einmal ausführen. :) Obwohl ich keine Ahnung habe, wie man dies effizient berechnet (effiziente O-Algorithmen waren etwas, in dem ich immer schlecht war .. und eines der wenigen Fächer an der IT-Hochschule, in denen ich ein paar Mal wiederholen musste), scheint es so eine sehr interessante herausforderung. Ich bin gespannt, welche Antworten die Leute haben.
Kevin Cruijssen
2
Gibt es ein funktionierendes Beispiel? Es wäre ein guter Ausgangspunkt, sowohl in Bezug auf die Korrektheit als auch für den Vergleich der Geschwindigkeit.
Maxb

Antworten:

6

Python 2.7 / Gurobi n = 9

Diese Lösung ist eine sehr direkte Anwendung von Gurobis ILP-Löser für die Booleschen Mixed-Integer-Probleme (MIP).

Der einzige Trick besteht darin, die Symmetrie im 1er-Komplement zu ermitteln, um die Problemgröße zu halbieren.

Mit der zeitlich begrenzten "kostenlosen" Lizenz von Gurobi LLC sind wir auf 2000 Einschränkungen beschränkt, aber das Lösen von 10 del 1 liegt auf meinem Laptop ohnehin weit außerhalb der 60-Sekunden-Frist.

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 hat die optimale Lösungsgröße 31 (siehe zB) Gurobi zeigt, dass keine symmetrische Lösung der Größe 30 existiert (Rückgabeproblem nicht realisierbar) Muster von ganzen Zahlen 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 255oder0 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

Jayprich
quelle
Sie haben den Rekord "Schnellste unendliche Prämie" gebrochen?
user202729
Ich sehe hier keine Prämie, was meinst du?
Jayprich
@ user202729 Ja .. Ich habe es zu niedrig eingestellt. Ich hätte es auf n = 10
einstellen sollen
Tatsächlich ist es nicht einfach, es bei n = 9 zu lösen. Deshalb verwendet OP eine vorhandene Bibliothek (die besser sein soll als eine handgeschriebene Lösung wie meine).
User202729
1
Danke @ChristianSievers Ich sehe, dass MO behauptet, 10,2 habe nur asymmetrische Optima, die ich weder widerlegen noch verifizieren kann. Wenn ich die Abkürzung für die Symmetrieannahme entferne, die bis zu n = 9 funktioniert, stellt sich heraus, dass Gurobi in der erforderlichen Zeit immer noch bis zu n = 9 lösen kann.
Jayprich
3

C ++, n = 6

Brute Force mit kleinen Optimierungen.

#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';
}

Lokal ausführen:

[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
user202729
quelle
1
Vor allem, um andere zu ermutigen, ihren Code zu veröffentlichen, wenn er schneller ist als meiner.
user202729
Bitte? ... (Hinweis: Dies ist ein Beispiel für ein Set-Cover-Problem.)
user202729
1
Ich arbeite dran. Ich kann mir einfach keine kluge Methode einfallen lassen. Wenn sonst niemand eine Antwort veröffentlicht, werde ich meine aufstellen, die bis jetzt nur n = 4 betragen kann.
Mypetlion