odwracalny predykat "binarny do numeru"

Question

Jaki jest najlepszy sposób konwertowania bitów binarnych (może to być na przykład lista 0/1) na liczby w odwracalny sposób. Napisałem natywny predykat w swi, ale czy istnieje lepsze rozwiązanie? Najlepsze odniesieniu

Answer 1

Zastosowanie CLP (FD) ograniczeń, na przykład:

:- use_module(library(clpfd)). 

binary_number(Bs0, N) :- 
     reverse(Bs0, Bs), 
     foldl(binary_number_, Bs, 0-0, _-N). 

binary_number_(B, I0-N0, I-N) :- 
     B in 0..1, 
     N #= N0 + B*2^I0, 
     I #= I0 + 1. 

Przykład wyszukiwania:

?- binary_number([1,0,1], N). 
N = 5. 

?- binary_number(Bs, 5). 
Bs = [1, 0, 1] . 

?- binary_number(Bs, N). 
Bs = [], 
N = 0 ; 
Bs = [N], 
N in 0..1 ; 
etc. 

Answer 2

Rozwiązanie

Odpowiedź ta ma na celu dostarczenie orzeczenie binary_number/2 który przedstawia zarówno logical-purity jak i najlepsze właściwości zakończenia. Użyłem when/2 w celu zatrzymania zapytań takich jak canonical_binary_number(B, 10) przed przejściem do nieskończonej pętli po znalezieniu pierwszego (unikalnego) rozwiązania. Istnieje oczywiście kompromis, program ma teraz zbędnych celów.

canonical_binary_number([0], 0). 
canonical_binary_number([1], 1). 
canonical_binary_number([1|Bits], Number):- 
    when(ground(Number), 
     (Number > 1, 
      Pow is floor(log(Number)/log(2)), 
      Number1 is Number - 2^Pow, 
      ( Number1 > 1 
      -> Pow1 is floor(log(Number1)/log(2)) + 1 
      ; Pow1 = 1 
     ))), 
    length(Bits, Pow), 
    between(1, Pow, Pow1), 
    length(Bits1, Pow1), 
    append(Zeros, Bits1, Bits), 
    maplist(=(0), Zeros), 
    canonical_binary_number(Bits1, Number1), 
    Number is Number1 + 2^Pow. 

binary_number(Bits, Number):- 
    canonical_binary_number(Bits, Number). 
binary_number([0|Bits], Number):- 
    binary_number(Bits, Number). 

Czystość i zakończenie

I twierdzą, że to orzeczenie przedstawia logical-purity z budowy. Mam nadzieję, że otrzymałem to prawo od tych odpowiedzi: one, two i three.

Dowolny cel z właściwymi argumentami zostaje zakończony. Jeśli argumenty muszą być sprawdzane, najprostszym sposobem osiągnięcia tego celu jest za pomocą wbudowanej length/2:

binary_number(Bits, Number):- 
    length(_, Number), 
    canonical_binary_number(Bits, Number). 

?- binary_number(Bits, 2+3). 
ERROR: length/2: Type error: `integer' expected, found `2+3' 
    Exception: (6) binary_number(_G1642009, 2+3) ? abort 
% Execution Aborted 
?- binary_number(Bits, -1). 
ERROR: length/2: Domain error: `not_less_than_zero' expected, found `-1' 
    Exception: (6) binary_number(_G1642996, -1) ? creep 

Przykład zapytania

?- binary_number([1,0,1|Tail], N). 
Tail = [], 
N = 5 ; 
Tail = [0], 
N = 10 ; 
Tail = [1], 
N = 11 ; 
Tail = [0, 0], 
N = 20 . 

?- binary_number(Bits, 20). 
Bits = [1, 0, 1, 0, 0] ; 
Bits = [0, 1, 0, 1, 0, 0] ; 
Bits = [0, 0, 1, 0, 1, 0, 0] ; 
Bits = [0, 0, 0, 1, 0, 1, 0, 0] ; 
Bits = [0, 0, 0, 0, 1, 0, 1, 0, 0] . 

?- binary_number(Bits, N). 
Bits = [0], 
N = 0 ; 
Bits = [1], 
N = 1 ; 
Bits = [1, 0], 
N = 2 ; 
Bits = [1, 1], 
N = 3 ; 
Bits = [1, 0, 0], 
N = 4 ; 
Bits = [1, 0, 1], 
N = 5 . 

Answer 3

gry z bitami ...

binary_number(Bs, N) :- 
    var(N) -> foldl(shift, Bs, 0, N) ; bitgen(N, Rs), reverse(Rs, Bs). 

shift(B, C, R) :- 
    R is (C << 1) + B. 

bitgen(N, [B|Bs]) :- 
    B is N /\ 1 , (N > 1 -> M is N >> 1, bitgen(M, Bs) ; Bs = []). 

Answer 4

Oto rozwiązanie, o którym myślałem, a raczej to, co, jak miałem nadzieję, istnieje.

:- use_module(library(clpfd)). 

binary_number(Bs, N) :- 
    binary_number_min(Bs, 0,N, N). 

binary_number_min([], N,N, _M). 
binary_number_min([B|Bs], N0,N, M) :- 
    B in 0..1, 
    N1 #= B+2*N0, 
    M #>= N1, 
    binary_number_min(Bs, N1,N, M). 

Rozwiązanie to wygasa również dla zapytań takich jak:

?- Bs = [1|_], N #=< 5, binary_number(Bs, N).