Разделение списка в прологе

Question

Я пытаюсь создать предикат Prolog, в котором по заданному списку видно, можно ли разделить этот список на два списка, которые суммируются в одну и ту же сумму.

У меня есть предикат суммы рабочего списка, поэтому я использую его в своем предикате разбиения. Сначала я попытался закодировать предикат, чтобы увидеть, равен ли первый элемент списка сумме остальной части списка ([2,1,1]). Это то, что я имею в этой ситуации.

partitionable([X|Y]) :-
   sum([X],SUM),
   sum([Y],SUM2),
   SUM = SUM2.

Тем не менее, я получаю это сообщение об ошибке:

ERROR: is/2: Arithmetic: `[]/0' is not a function. 

Я хотел бы, чтобы эта часть работала до того, как я углублюсь в рекурсию для остальной части списка, хотя я запутался в том, что говорит это сообщение, так как я не написал '[]/0' function, Любая помощь приветствуется.

Answer 1

Чтобы разбить список на две непересекающиеся подпоследовательности, мы используем list_subseq_subseq/3:

list_subseq_subseq([]    ,[]    ,[]).
list_subseq_subseq([X|Xs],[X|Ys],Zs) :-
   list_subseq_subseq(Xs,Ys,Zs).
list_subseq_subseq([X|Xs],Ys,[X|Zs]) :-
   list_subseq_subseq(Xs,Ys,Zs).

Для выполнения целочисленной арифметики мы используем clpfd:

:- use_module(library(clpfd)).

Давайте сложим все это вместе! В следующем примере запроса мы разбиваем список [1,2,3,4,5,6,7]:

?- Xs = [1,2,3,4,5,6,7],
   sum(Xs,#=,Total),
   Half*2 #= Total,
   list_subseq_subseq(Xs,Ys,Zs),
   sum(Ys,#=,Half),
   sum(Zs,#=,Half).
  Xs = [1,2,3,4,5,6,7], Total = 28, Half = 14, Ys = [1,2,4,7], Zs = [3,5,6]
; Xs = [1,2,3,4,5,6,7], Total = 28, Half = 14, Ys = [1,2,5,6], Zs = [3,4,7]
; Xs = [1,2,3,4,5,6,7], Total = 28, Half = 14, Ys = [1,3,4,6], Zs = [2,5,7]
; Xs = [1,2,3,4,5,6,7], Total = 28, Half = 14, Ys = [1,6,7]  , Zs = [2,3,4,5]
; Xs = [1,2,3,4,5,6,7], Total = 28, Half = 14, Ys = [2,3,4,5], Zs = [1,6,7]
; Xs = [1,2,3,4,5,6,7], Total = 28, Half = 14, Ys = [2,5,7]  , Zs = [1,3,4,6]
; Xs = [1,2,3,4,5,6,7], Total = 28, Half = 14, Ys = [3,4,7]  , Zs = [1,2,5,6]
; Xs = [1,2,3,4,5,6,7], Total = 28, Half = 14, Ys = [3,5,6]  , Zs = [1,2,4,7]
; false.

Answer 2

Становится лучше!

Для недетерминированного разбиения списков нам не нужно реализовывать рекурсивный вспомогательный предикат, такой как list_subseq_subseq/3 если мы используем правильную комбинацию мета-предикат / предикат!

В этом ответе мы используем tpartition/4 в качестве мета-предиката и предиката "reified wild-card" (*)/2 как предикат перешел к tpartition/4, (*)/2 можно определить так:

_ * true.
_ * false.

Давайте положим tpartition/4 использовать с (*)/2 и ограничения clpfd (#=)/2 а также sum/3:

?- use_module(library(clpfd)).   % use clp(FD) library
true.

?- ABs = [1,2,3,4,5,6,7],        % same data as in the earlier answer
   sum(ABs,#=,NN),
   N*2 #= NN,
   tpartition(*,ABs,As,Bs),
   sum(As,#=,N),
   sum(Bs,#=,N).
  NN = 28, N = 14, ABs = [1,2,3,4,5,6,7], As = [1,2,4,7], Bs = [3,5,6] 
; NN = 28, N = 14, ABs = [1,2,3,4,5,6,7], As = [1,2,5,6], Bs = [3,4,7]
; NN = 28, N = 14, ABs = [1,2,3,4,5,6,7], As = [1,3,4,6], Bs = [2,5,7]
; NN = 28, N = 14, ABs = [1,2,3,4,5,6,7], As = [1,6,7]  , Bs = [2,3,4,5]
; NN = 28, N = 14, ABs = [1,2,3,4,5,6,7], As = [2,3,4,5], Bs = [1,6,7]    
; NN = 28, N = 14, ABs = [1,2,3,4,5,6,7], As = [2,5,7]  , Bs = [1,3,4,6]    
; NN = 28, N = 14, ABs = [1,2,3,4,5,6,7], As = [3,4,7]  , Bs = [1,2,5,6]
; NN = 28, N = 14, ABs = [1,2,3,4,5,6,7], As = [3,5,6]  , Bs = [1,2,4,7]
; false.

Answer 3

Я также предложил бы другое решение для проблемы раздела. Предикат помощника помогает сократить список два списка. Например, [1,2,3] можно сократить:

[1,2] (левая сторона) и [3](правая сторона) или

[3](левая сторона) и [1,2] (правая сторона).

helper([],[],[],0,0).  
helper([X|XS],[X|L],R,SUML,SUMR):-helper(XS,L,R,SUMN,SUMR),SUML is SUMN+X. 
helper([X|XS],L,[X|R],SUML,SUMR):-helper(XS,L,R,SUML,SUMN),SUMR is SUMN+X.
partition(S,L,R):-helper(S,L,R,X,X).

Выход:

1 ?- partition([1,2,3,4],L,R).
L = [1, 4],
R = [2, 3] ;
L = [2, 3],
R = [1, 4] ;
false.

Answer 4

Я считаю, что передача X как [X] обязательна, поскольку X - это просто элемент (число 2 в вашем примере). Y, с другой стороны, сам по себе является списком, и его не следует помещать в другой список. Вот модифицированная версия:

partitionable([X|Y]) :- sum([X],SUM), sum(Y,SUM2), SUM=SUM2.
sum([X|Y],SUM) :- sum(Y, SUBSUM), SUM is SUBSUM + X.
sum([X],SUM) :- X=SUM.

partitionable([2,1,1]) возвращает истину в моем случае.

Изменить: так как вы не используете is/2 это может быть ошибкой в sum сказуемое.

На другой ноте: как я понимаю ваш вопрос, вам не нужно решение для partitionable но сообщение об ошибке вы получили. Тем не менее, вот мой взгляд на его реализацию (возможно, спойлер впереди):

/* partitionable(X)
 * If a 2-partition of X exists where both sublists have the same sum, then X
 * is considered partitionable.
 */
partitionable(X) :- partition(X, A, B), sum(A, SUM), sum(B, SUM2), SUM =:= SUM2, !.

/* partition(X, A, B)
 * X is split in two lists A and B and will, during backtracking, bind A and B to
 * ALL permutations of the list partition, including permutations for each list.
 */
partition([], [], []).
partition([X|Y], A, B) :- partition(Y, R, B), extract(X, A, R).
partition([X|Y], A, B) :- partition(Y, A, R), extract(X, B, R).

/* extract(X, L, R)
 * Extracts exactly one element X from L and unify the result with R.
 */
extract(X, [H|T], R) :- X = H, R = T.
extract(X, [H|T], R) :- R = [H|R2], extract(X, T, R2).

sum([X|Y],SUM) :- sum(Y, SUBSUM), SUM is SUBSUM + X.
sum([X],SUM) :- X = SUM.

Answer 5

Может быть, я думаю об этом, но...

Если под "разбиением списка" вы подразумеваете "разрезать список на две части, сохраняя порядок, а не создавая различные перестановки списка), то не похоже, что решение должно быть более сложным, чем что-то вроде этого:

partitionable( Ns ) :-
  append( Prefix , Suffix , Ns ) ,
  compute_sum(Prefix,Sum) ,
  compute_sum(Suffix,Sum) .

compute_sum( Ns , S ) :- compute_sum(Ns,0,S) .

compute_sum( []     , S , S ) .
compute_sum( [N|Ns] , T , S ) :- T1 is N+T , compute_sum(Ns,T1,S) .

Если вы хотите избежать использования встроенных модулей, вы можете сделать что-то вроде этого, что дает дополнительные преимущества элегантности при минимизации обхода списка:

partitionable( List ) :-
  sum_prefix( List , Sum , Sfx ) ,
  sum_prefix( Sfx  , Sum , []  ) .

sum_prefix( List , Sum , Suffix ) :- sum_prefix(List,0,Sum,Suffix) .

sum_prefix( Suffix   , Sum , Sum , Suffix ) .
sum_prefix( [H|List] , Acc , Sum , Suffix ) :-
  Acc1 is Acc+H ,
  sum_prefix(List,Acc1,Sum,Suffix)
  .