两个列表的整数约束和差异

Question

我试图找到一个值 score，可以从两个等长列表 Xs, Ys 强制计算为：

for i in len(Xs):
    if Xs[i] == Ys[i]:
        score++
    else:
        score--

所以我们的想法是基本上检查两个列表中从左到右的每个元素，如果这些元素相同则递增分数，否则递减分数。例如：

score([1,2,3], [1,2,3]) == 3
score([1,2,3], [1,2,1]) == 1
score([1,2,3], [3,2,1]) == -1
score([1,2,3], [3,1,2]) == -3

我想我实际上把程序写成了：

score(Xs, Ys, C) ?=>
    Xs = [], Ys = [], C = 0.

score(Xs, Ys, C) =>
    Xs = [XH|XT],
    Ys = [YH|YT],
    if (XH #= YH) then
        C #= C1 + 1
    else
        C #= C1 - 1
    end,
    score(XT, YT, C1).

当我查询 score:

时，代码给出了正确的结果

score([1,2,3], [1,2,3], S).
    S = 3 ?;

score([1,2,3], [1,2,1], S).
    S = 1 ?;

score([1,2,3], [3,2,1], S).                                      
    S = -1 ?;

score([1,2,3], [3,1,2], S).                                      
    S = -3 ?;

但是，当我尝试生成产生分数的列表时，代码只生成分数为 3 的相同列表：

S :: -3..3, Ls = new_list(3), Ls :: 1..3, score([1,2,3], Ls, S), solve([Ls, S]).

S = 3
Ls = [1,2,3] ?;

no

我想生成所有列表，对应所有可能的分数，我觉得我必须修改基本情况，但我不知道如何:)

编辑：我也尝试做一个尾递归类型的解决方案，它在查询分数时再次给出正确的结果，但它只能生成相同的列表。

score(Xs, Ys, C) ?=>
    score_helper(Xs, Ys, 0, C).

score_helper([], _, Cur, C) ?=>
    C = Cur.

score_helper(Xs, Ys, Cur, C) ?=>
    Xs = [XH|XT],
    Ys = [YH|YT],
    if (XH = YH) then
        score_helper(XT, YT, Cur+1, C)
    else
        score_helper(XT, YT, Cur-1, C)
    end.

Answer 1

如果您正在使用约束求解器（例如 cp、sat 等），那么只需使用 sum 即可：

import cp. 

go ?=> 
  X=new_list(3),
  Y=new_list(3),
  X::1..3, 
  Y::1..3, 
  Z #= sum([cond(X[I] #= Y[I], 1,-1) : I in 1..3]),
  solve(X++Y),
  println([x=X,y=Y,z=Z]), 
  fail,
  nl.
go => true.

要点是可以在列表推导中使用约束（此处X[I] #= Y[I]）。

还是要求不使用约束？

编辑：另一种 CP 方法如下（使用 Picat v3 支持的“Prolog”样式。这使用等价性 (#<=>) 进行检查：

go3 ?=>
  Y = [1,2,3],
  X = new_list(3),
  X :: 1..3,
  Score :: [-1,1],
  score3(X,Y,0,Score),
  solve(X ++ [Score]),
  println(x=X),
  println(score=Score),
  nl,
  fail,
  nl.
go3 => true.


score3([], [], Score,Score).
score3([XH|XT], [YH|YT], Score0, Score) :-
  (XH #= YH) #<=> (Score1 #= Score0 + 1),
  score3(XT, YT, Score1,Score).

您的方法的一个问题是您将约束相等性检查 (#=) 与传统相等性（== 和 =）混合使用，这可能不会给出预期的结果。

还有另一种使用相同原理但在 foreach 循环内的方法：

 go2 ?=>
   Y = [1,2,3],
   N = Y.len,
   X = new_list(N),
   X :: 1..max(Y),
   Scores = new_list(N),
   Scores :: [-1,1],
   foreach(I in 1..X.len)
      X[I] #= Y[I] #<=> Scores[I] #= 1
   end,
   Z #= sum(Scores),
   solve(X ++ Scores),
   println([x=X,y=Y,scores=Scores,z=Z]),
  fail,
  nl.
go2 => true.

两个列表的整数约束和差异

Integer constraints and difference of two lists

list

logic-programming

constraint-programming

picat