Geek asks and answers

Evaluate all possible interpretations in OCaml

I need to evaluate whether two formulas are equivalent or not. Here I use a simple formula definition, which is a prefix formula.

For example, And(Atom("b"), True)means b and true, and And(Atom("b"), Or(Atom("c"), Not(Atom("c"))))means(b and (c or not c))

My idea is simple, get all the atoms, apply each combination (for my cases I will have 4 combinations that are true-true, true-false, false-true and false-false). The fact is, I don’t know how to create these combinations.

Currently, I know how to get all the involvement of atoms, so if there are 5 atoms, I have to create 32 combinations. How to do it in OCaml?

+3
source share
2 answers

, combinations n, n; (.. ). :

let rec combinations = function
  | 0 -> [[]]
  | n ->
    let rest = combinations (n - 1) in
    let comb_f = List.map (fun l -> false::l) rest in
    let comb_t = List.map (fun l -> true::l) rest in
    comb_t @ comb_f

0, n > 0 n-1 false true n.

, :

let rec combinations_to_string = function
  | [] -> ""
  | x::xs ->
      let rec bools_to_str = function
        | [] -> ""
        | b::bs -> Printf.sprintf "%s%s" (if b then "T" else "F") (bools_to_str bs)
      in
      Printf.sprintf "[%s]%s" (bools_to_str x) (combinations_to_string xs)

:

let _ =
  let n = int_of_string Sys.argv.(1) in
  let combs = combinations n in
  Printf.eprintf "combinations(%d) = %s\n" n (combinations_to_string combs)

:

> ./combinations 3
combinations(3) = [TTT][TTF][TFT][TFF][FTT][FTF][FFT][FFF]
+4

, : Count!

4 , 0 15 (2 ^ 4 - 1) - . for-loop, :

let size = 4 in
(* '1 lsl size' computes 2^size *)
for i = 0 to (1 lsl size) - 1 do
   (* from: is the least significant bit '1'? *)
   let b0 = 1 = ((i / 1) mod 2) in
   let b1 = 1 = ((i / 2) mod 2) in
   let b2 = 1 = ((i / 4) mod 2) in
   (* to: is the most significant bit '1'? *)
   let b3 = 1 = ((i / 8) mod 2) in
   (* do your thing *)
   compute b0 b1 b2 b3
done

, , , . / , ..; , , , . , . , . .

, , , . . = 16 65535 * sizeof (type) - ! sizeof (type).

: NP-complete, , , .

+1

More articles:


All Articles