OCaml에서 가능한 모든 해석을 평가하십시오.

Question

두 공식이 동등한 지 아닌지 평가해야합니다. 여기서 접두어 수식 인 수식의 간단한 정의를 사용합니다. And(Atom("b"), Or(Atom("c"), Not(Atom("c")))) 내 아이디어는 간단하다 (b and (c or not c))

, 내 경우에 (모든 조합을 적용, 모든 원자를 얻을 의미 예를 들어

이 And(Atom("b"), True) 내가 진정한-해당하는 4 조합을해야합니다, b and true 의미, true- false, false-true 및 false-false). 것은, 나는이 조합을 만드는 방법을 모른다.

현재로서는 모든 원자를 얻는 방법을 알고 있으므로 원자 수가 5 개인 경우 32 조합을 만들어야합니다. 어떻게 OCaml에서 그것을 할 수 있습니까?

Answer 1

좋아, 그럼 당신은 무엇이 필요합니까? n의 모든 불리언 조합을 생산할 함수 combinations n입니다; 부울 목록 목록으로 표현하자 (즉, 변수의 단일 지정은 부울 목록입니다). 길이 0의 하나의 빈 조합이

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 

및 n > 0 위해 우리는 n-1의 조합을 생산하고 false로 접두사와 true와 길이 n의 모든 가능한 조합을 생산하기 위해 :이 함수는 그 일을 할 것입니다.

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) 

이 얻을 :

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) 

을 다음으로 모든 테스트 :

당신은 이러한 조합을 인쇄하는 기능을 쓸 수

은의 말을하자

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

Answer 2

당신이 만약 부울 목록을 고정 길이의 비트 목록으로 생각하면 아주 간단한 해결책이 있습니다. 백작!

4 개의 부울을 모두 조합하려면 0에서 15까지 (2^4 - 1)로 계산하고 각 비트를 부울 중 하나로 해석합니다. 단순화를 위해 나는에 대한 - 루프 A를 사용합니다,하지만 당신은 또한 재귀와 함께 할 수 있습니다 : 당신은 루프의 몸이 더 일반적인 만들 수 있습니다 물론

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 (유형) 메모리가 필요합니다. 크기가 기하 급수적으로 커지고 있습니다! 위의 솔루션은 크기 (유형)의 일정량의 메모리 만 필요합니다.

그리고 과학적으로 : 문제는 NP 완료입니다. 정확한 솔루션을 원한다면 기하 급수적으로 걸릴 것입니다.