让 Prolog 的 CLPFD 知道排列和其他对称性

Question

use_module(library(clpfd)).

CLPFD 似乎并没有很快意识到

length(L, 9), L ins 1..9, all_distinct(L), foreach(label(L), sum(L, #=, X))
X=45.

（我试过 length(L, 4), all_distinct(L), L ins 1..4, sum(L, #=, X), label([X]). 试图通知我 1 + 2 + 3 + 4 = 7，所以我可能误解了什么）。

length(L, 9), L ins 1..9, all_distinct(L), bagof(L, label(L), Ls), length(Ls, X).

应该给哪位X = 362880.也有类似问题

两者似乎都在 O(N!) 中执行 length(L, N)，这当然是因为我们正在枚举 L 的每一种可能的排列来得出我们的结论。

这些边缘情况当然可以用更简单的解决方案代替，我们可以在任何地方使用它们。但是例如，如果能够让 CLPFD 能够推断出 length(L, N - 1), L ins 1..N, all_distinct(L) 我们可以计算 sum(L, #=, X) 得到 X in N (N - 1) / 2 - N..N (N - 1) / 2 - 1.

我是否遗漏了 CLPFD 的某些方面或计算标签而不枚举它们的谓词，以及一种让 CLPFD 了解 sum 的鸽巢原理 + 结合性 + 交换性的方法，还是为这些特定情况编写谓词？

Answer 1

在 SWI Prolog 8.1 中：

我不太了解你似乎 "label" 太早或太急切（"foreach of the labelings" 闻起来有鱼腥味）

尝试

?- length(L, 9), L ins 1..9, all_distinct(L), sum(L, #=, X), X = 45, label(L).

立即returns与

L = [1, 2, 3, 4, 5, 6, 7, 8, 9],
X = 45

类似于

?- length(L, 4), all_distinct(L), L ins 1..4, sum(L, #=, X), label(L).

这给出了

L = [1, 2, 3, 4],
X = 10 ;

我不确定这里发生了什么，但再次 label([X]) 听起来不对。

?- length(L, 4), all_distinct(L), L ins 1..4, sum(L, #=, X), label([X]).
L = [_7950, _7956, _7962, _7968],
X = 7,
_7950 in 1..4,
_7950+_7956+_7962+_7968#=7,
all_distinct([_7950, _7956, _7962, _7968]),
_7956 in 1..4,
_7962 in 1..4,
_7968 in 1..4 ;

我确实认为 CLP(FD) 没有注意到上面的解决方案没有解决方案，因为它只输出约束。

但是试试

?- length(L, 4), all_distinct(L), L ins 1..4, sum(L, #=, X), label([X]), label(L).
L = [1, 2, 3, 4],
X = 10

正确。

But for example it would be nice to be able have CLPFD be able to reason that in length(L, N - 1), L ins 1..N, all_distinct(L) we can calculate sum(L, #=, X) to have X in N (N - 1) / 2 - N..N (N - 1) / 2 - 1.

证明整数算术的绝对一般定理，而不是约束传播。那会很好，但我认为它不会走那么远。

让 Prolog 的 CLPFD 知道排列和其他对称性

Making Prolog's CLPFD aware of permutations and other symmetries

permutation

prolog

combinatorics

clpfd