实现算法
奎因-麦克卢斯基算法将析取中的析取(如\lnot x_0 \land \lnot x_1 \land \lnot x_2 \land \lnot x_3 \lor\\ x_0 \land \lnot x_1 \land x_2 \land \lnot x_3 \lor\\ \lnot x_0 \land x_1 \land x_2 \land \lnot x_3 \lor\\ \lnot x_0 \land \lnot x_1 \land \lnot x_2 \land x_3 \lor\\ \lnot x_0 \land x_1 \land \lnot x_2 \land x_3 \lor\\ x_0 \land x_1 \land \lnot x_2 \land x_3 \lor\\ \lnot x_0 \land x_1 \land x_2 \land x_3 \lor\\ x_0 \land x_1 \land x_2 \land x_3 )合并为等效析取( x_1 \land x_3 \lor\\ \lnot x_0 \land \lnot x_1 \land \lnot x_2 \lor\\ \lnot x_0 \land x_1 \land x_2 \lor\\ x_0 \land \lnot x_1 \land \lnot x_2 \land x_3 )中的较少的析取(D2)，方法是合并如下：x_0\land x_1\lor\lnot x_0\land x_1 \iff (x_0\lor\lnot x_0)\land x_1\iff x_1。
https://www.mathematik.uni-marburg.de/~thormae/lectures/ti1/code/qmc/将生成用于体验的测试用例。
您的任务
您的任务是编写一个函数，将任何分离转换为最小析取计数的等效析取。
标题中的QMC算法是一个草率的总结，仅仅是一个推荐，没有硬性要求。
您可以以任何合适的方式对数据进行编码，即\lnot x_1 \land \lnot x_2 \land x_3可以成为
- (14,8)
- …
我是code-golf。最短代码获胜。
回答 2
Code Golf用户
发布于 2023-05-18 09:18:46
卡米拉利什，139个字节
(defun s m \let-seq(def a \⍸ \= 1 \⌼ $(foldl1 +)@/= m m)(↩ (= 0 \⍴ a) m)(def p m$[⍎ a])\^⍪ p \⍠ m \[tie@* ⍎ $(foldl1 =)] p)"Ungolfed"：
(⍥← s m \○⊢¨
(○← a \⍸ \= 1 \⌼ $(⌿⊙← +)∘≠ m m) ; Find all possible rows we can join.
(↩ (= 0 \⍴ a) m) ; If we can't join anything, yield.
(○← p m$[⍎ a]) ; Determine the contents of the rows in the matrix to be joined.
\^⍪ p \⍠ m \[⌿⊙⍧∘* ⍎ $(⌿⊙← =)] p) ; Adjoin the new row, remove the merged two.本质上，该算法在矩阵中找到表示表达式的两行(每个单元格，要么是-1，1，要么是0，表示布尔值要么被否定，要么被当作给定，或者不使用)，这些行最多有一个条目不同。然后，如果找不到这样的行，则算法返回原始矩阵。如果存在至少一个这样的对，则将其从矩阵中删除，将两者之间的差异计算为掩码(例如，对于-1 -1 1 1和-1 -1 1 -1，掩码为1 1 1 0)，然后乘以该对的第一(或等效的第二)元素，形成表达式矩阵中的新条目。
一些测试用例等：
Code Golf用户
发布于 2023-05-14 04:33:47
哈斯克尔，340个字节
import Data.Bits;import Data.List;import Data.List.Ordered
o d[]=d;o _ s=s
p(a:b:c)|a==b=a|0<1=p(b:c)
q(_,b)(c,d)=c.&.b==c.&.d
r t s=and[or[q f e|e<-s]|f<-t]
s(a,b)(c,d)=[(a.&.complement x,b.&.d)|a==c,let x=xor b d,1==popCount x]
t d=nubSort$concatMap(\c->o[c]$concatMap(s c)d)d
u d=head$sortOn length$filter(r d)$subsequences$p$iterate t d在这里，一个分离器用(significantbitmask,setbits)表示，由q和s摆弄。s组合两个分隔符，如果它们具有相同的significantbitmask，并且恰好在一个位内不同。如果与任何人结合，o[c]可以防止分离子消失。u计算一个最小的分离：t在d中合并反价物直到p不再合并，然后它过滤r足够的子集，因为合并可以产生多余的分离子。
https://codegolf.stackexchange.com/questions/260907
复制
腾讯云开发者
