arXiv:2605.24845cs.AImath.CO2026-05

用可编程语言自动求解组合计数难题,省去手动推导。

Solving Combinatorial Counting Problems with Weighted First-Order Model Counting

  • 设计新型声明式语言Cofola,直接表达集合、排列等常见计数对象
  • 将复杂计数问题转化为加权一阶模型计数,保持对称性提升效率
  • 适合需要快速建模组合问题的研究者和工程师

组合计数问题广泛存在于人工智能、统计学和离散数学中。无论是枚举满足结构与算术约束的子集、多重集、排列、划分或组合,求解仍常需手动处理。闭式推导虽强大但脆弱,而朴素编码至命题模型计数或约束满足会破坏使计数可解的交换性。本文提出Cofola(COmbinatorial counting LAnguage with First-Order logic),一种带类型的声明式语言,其原语为日常计数问题中反复出现的组合对象,包括集合、袋装、元组、序列、环、划分和组合,并支持自然的关系与算术约束。其语义将每个Cofola程序映射为明确的组合计数问题,三阶段编译流程(预处理、分解、对称保全编码)将其转化为带有系数提取约束的加权一阶模型计数(WFOMC)实例。为保持在已知域可提升片段内,编码将不可区分实体分组,通过词典序打破无序分组的对称性,并通过顺序公理编码序列与环。在一系列代表性组合计数问题上,涵盖教科书级数学题到先前框架无法表达的多对象场景,Cofola生成简洁规范,提供统一且实用的端到端求解管道。

原文摘要 · Abstract (English)

Combinatorial counting problems pervade artificial intelligence, statistics, and discrete mathematics. Whether the task is enumerating subsets, multisets, permutations, partitions, or compositions under structural and arithmetic constraints, solving it remains a stubbornly manual exercise. Closed-form derivations are powerful but brittle, while naive encodings to propositional model counting or constraint satisfaction destroy the exchangeability that makes counting tractable in the first place. We present Cofola (COmbinatorial counting LAnguage with First-Order logic), a typed declarative language whose primitives are the combinatorial objects that recur in everyday counting questions, including sets, bags, tuples, sequences, circles, partitions, and compositions, together with natural relational and arithmetic constraints over them. A denotational semantics maps every Cofola program to a well-defined combinatorial counting problem, and a three-phase compilation pipeline (preprocessing, decomposition, and symmetry-preserving encoding) reduces this problem to a weighted first-order model counting (WFOMC) instance augmented with coefficient-extraction constraints. To stay inside known domain-liftable fragments whenever possible, the encoding groups indistinguishable entities, breaks the symmetry of unordered groupings lexicographically, and encodes sequences and circles via order axioms. On a suite of representative combinatorial counting problems, ranging from textbook math problems to multi-object scenarios that the closest prior framework cannot express, Cofola produces concise specifications and a uniform solving pipeline that is practical end-to-end.

组合计数形式化语言模型计数自动推理

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。