当前位置：文江博客话题详情

评估 OCaml 中所有可能的解释

发布于 2024-10-21 00:04:08 字数 362 浏览 1 评论 0原文

我需要评估两个公式是否等价。这里我用一个简单的公式定义，就是前缀公式。

例如，And(Atom("b"), True) 表示 b 和 true，而 And(Atom("b"), Or(Atom( "c"), Not(Atom("c")))) 表示 (b 和 (c 或 not c))

我的想法很简单，获取所有原子，应用每个组合（对于我的情况，我将有 4 种组合，即真-真、真-假、假-真和假-假）。问题是，我不知道如何创建这些组合。

现在，我已经知道如何获得所有涉及的原子，所以如果有 5 个原子，我应该创建 32 种组合。如何在 OCaml 中做到这一点？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

野の 2024-10-28 00:04:08

好的，所以您需要的是一个函数 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 > 为 1。 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]

Ok, so what you need is a function combinations n that will produce all the booleans combinations of length n; let's represent them as lists of lists of booleans (i.e. a single assignment of variables will be a list of booleans). Then this function would do the job:

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

There is only one empty combination of length 0 and for n > 0 we produce combinations of n-1 and prefix them with false and with true to produce all possible combinations of length n.

You could write a function to print such combinations, let's say:

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)

and then test it all with:

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)

to get:

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

回复收藏 0 原文

情场扛把子 2024-10-28 00:04:08

如果您将布尔值列表视为固定长度的位列表，那么有一个非常简单的解决方案：计数！

如果您想要 4 个布尔值的所有组合，请从 0 数到 15 (2^4 - 1)——然后将每一位解释为布尔值之一。为简单起见，我将使用 for 循环，但您也可以通过递归来完成：

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

当然，您可以使循环体更加通用，以便它根据上面给出的大小创建布尔值列表/数组ETC。;
关键是您可以通过枚举您正在搜索的所有值来解决这个问题。如果是这种情况，请计算所有整数直至您的问题大小。编写一个函数，从整数生成原始问题的值。把它们放在一起。

此方法的优点是您不需要在开始计算之前首先创建所有组合。对于大问题，这很可能会拯救你。对于相当小的 size=16，您将需要 65535 * sizeof(type) 内存 - 并且随着大小呈指数增长！上述解决方案仅需要 sizeof(type) 的恒定内存量。

为了科学的缘故：你的问题是NP完全，所以如果你想要精确的解决方案，它将需要指数时间。

If you think of a list of booleans as a list of bits of fixed length, there is a very simple solution: Count!

If you want to have all combinations of 4 booleans, count from 0 to 15 (2^4 - 1) -- then interpret each bit as one of the booleans. For simplicity I'll use a for-loop, but you can also do it with a recursion:

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

Of course you can make the body of the loop more general so that it e.g. creates a list/array of booleans depending on the size given above etc.;
The point is that you can solve this problem by enumerating all values you are searching for. If this is the case, compute all integers up to your problem size. Write a function that generates a value of your original problem from an integer. Put it all together.

This method has the advantage that you do not need to first create all combinations, before starting your computation. For large problems this might well save you. For rather small size=16 you will already need 65535 * sizeof(type) memory -- and this is growing exponentially with the size! The above solution will require only a constant amount of memory of sizeof(type).

And for science's sake: Your problem is NP-complete, so if you want the exact solution, it will take exponential time.

回复收藏 0 原文

~没有更多了~