Hapus beberapa bit dan hitung

26

Pertimbangkan semua 2^npanjang string biner yang berbeda ndan asumsikan n > 2. Anda diizinkan untuk menghapus b < n/2bit tepat dari masing-masing string biner, meninggalkan string yang n-btersisa. Jumlah string berbeda yang tersisa tergantung pada bit mana yang Anda hapus. Dengan asumsi tujuan Anda adalah untuk meninggalkan string yang tersisa sesedikit mungkin, tantangan ini adalah menulis kode untuk menghitung berapa sedikit yang dapat Anda tinggalkan sebagai fungsi n.

Contoh, n=3dan b = 1. Anda hanya dapat meninggalkan dua string 11dan 00.

Untuk n=9dan b = 1,2,3,4kita miliki70,18,6,2

Untuk n=8dan b = 1,2,3kita miliki40,10,4

Untuk n=7dan b = 1,2,3kita miliki20,6,2

Untuk n=6dan b = 1,2kita miliki12,4

Untuk n=5dan b = 1,2kita miliki6,2

Pertanyaan ini awalnya diajukan oleh saya pada tahun 2014 dalam bentuk berbeda di MO .

Masukan dan keluaran

Kode Anda harus mengambil bilangan bulat ndan mengeluarkan bilangan bulat tunggal untuk setiap nilai bmulai b = 0dan meningkat.

Skor

Skor Anda adalah yang terbesar nyang menyelesaikan kode Anda untuk semua b < n/2dalam waktu kurang dari satu menit pada PC berbasis Linux saya. Jika terjadi break tie, bkode Anda yang terbesar didapat untuk nkemenangan terbesar bersama . Dalam kasus tie break pada kriteria itu juga, kode tercepat untuk nilai-nilai terbesar ndan bmemutuskan. Jika waktunya dalam satu atau dua detik satu sama lain, jawaban yang diposting pertama menang.

Bahasa dan perpustakaan

Anda dapat menggunakan bahasa perpustakaan apa pun yang Anda suka. Karena saya harus menjalankan kode Anda, itu akan membantu jika itu gratis (seperti bir) dan bekerja di Linux.

Anush
sumber
Saya menganggap b > 0sebagai persyaratan input tambahan? Atau akan n=3dan b=0hanya menampilkan 2^nsebagai hasilnya?
Kevin Cruijssen
@KevinCruijssen Seharusnya 2^nmemang menghasilkan .
Anush
Juga, Anda mengatakan inputnya adalah tunggal ndan tunggal b, tetapi skornya adalah yang terbesar nyang menyelesaikan semua kode b < n/2dalam waktu kurang dari satu menit. Bukankah lebih baik memiliki satu input ndalam kasus itu, dan mengeluarkan semua hasil 0 <= b < n/2? Atau haruskah kita menyediakan dua program / fungsi: satu mengambil dua input ndan b, dan satu hanya mengambil input ndan mengeluarkan semua hasil dalam rentang 0 <= b < n/2?
Kevin Cruijssen
2
Yah, saya sudah meningkatkan tantangan Anda, jadi tidak bisa melakukannya lagi. :) Walaupun saya tidak tahu bagaimana cara menghitung ini secara efisien (algoritma O efisien adalah sesuatu yang saya selalu buruk pada .. dan salah satu dari beberapa mata pelajaran di perguruan tinggi IT yang harus saya ulangi beberapa kali), sepertinya tantangan yang sangat menarik. Saya ingin tahu jawaban apa yang diajukan orang.
Kevin Cruijssen
2
Apakah ada contoh kerja? Ini akan menjadi tempat yang baik untuk memulai, baik dari segi kebenaran, tetapi juga untuk perbandingan kecepatan.
Maks.

Jawaban:

6

Python 2.7 / Gurobi n = 9

Solusi ini sangat mudah digunakan solver Gurobi's ILP untuk boolean Mixed-Integer Problems (MIP).

Satu-satunya trik adalah mengambil simetri dalam komplemen 1 untuk membagi dua ukuran masalah.

Menggunakan lisensi "bebas" terbatas Gurobi LLC, kami dibatasi hingga 2000 kendala, tetapi menyelesaikan 10 del 1 masih di luar batas waktu 60 detik di laptop saya.

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 memiliki ukuran solusi optimal 31 (lihat misalnya) Gurobi tidak menunjukkan solusi simetris ukuran 30 ada (mengembalikan masalah tidak layak) .. [usaha saya untuk menunjukkan kelayakan asimetris pada 30 tetap tidak meyakinkan setelah runtuh 9,5 jam] misalnya bit pola bilangan bulat 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 255atau0 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
sumber
Anda memecahkan rekor "hadiah terhingga tak terbatas"?
user202729
Saya tidak melihat karunia apa pun di sini, apa maksud Anda?
jayprich
@ user202729 Ya .. Saya atur terlalu rendah. Seharusnya saya atur di n = 10 :)
Anush
Sebenarnya menyelesaikannya di n = 9 bukanlah hal yang mudah. Itu sebabnya OP menggunakan perpustakaan yang ada (yang seharusnya lebih baik daripada solusi tulisan tangan, seperti milik saya).
user202729
1
Terima kasih @ChristianSievers Saya melihat MO mengklaim bahwa 10,2 hanya memiliki optima asimetris yang tidak dapat saya tolak atau verifikasi. Jika saya menghapus pintasan asumsi simetri yang bekerja hingga n = 9 ternyata Gurobi masih dapat menyelesaikan hingga n = 9 pada waktu yang diperlukan.
jayprich
3

C ++, n = 6

Brute force dengan beberapa optimasi kecil.

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

Jalankan secara lokal:

[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
pengguna202729
sumber
1
Terutama untuk mendorong orang lain untuk memposting kode mereka jika lebih cepat dari saya.
user202729
Tolong? ... (catatan: Ini adalah contoh dari masalah cover set.)
user202729
1
Saya sedang mengerjakannya. Saya tidak bisa menemukan cara yang cerdas untuk melakukannya. Jika tidak ada orang lain yang memposting jawaban, saya akan memasang jawaban saya yang hanya bisa setinggi n = 4 sejauh ini.
mypetlion