Splitting a list into two lists equal in length in

问题:

I am writing a predicate in Prolog to divide a list into two equal in length lists. For example :

div([1,2,3,4] , X , Y).
X = [1,2].
Y = [3,4].

That's my code but it's not working :

div(L , L1 , L):- length(L) == length(L1).
div([ H | T ] , [ H | T1] , L2):- div(T , T1 , L2).

回答1:

Could be just:

div(L, A, B) :-
    append(A, B, L),
    length(A, N),
    length(B, N).

Read as "appending list A and list B results in original list L, length of A is some value N and also length of B is the same value N".

回答2:

Funny is this split which doesn't use length :

div(L, A, B) :-
    split(L, L, A, B).

split(B, [], [], B).

split([H|T], [_, _|T1], [H | T2], B) :-
    split(T, T1, T2, B).

For a list of 100 000 elements, it uses 50 001 inferences but 0,016 CPU, for the same list, lurker's code uses 50 015 inferences and 0,000 CPU.

回答3:

length(L) == length(L1)

is not how you compare lengths of lists in Prolog. It compares the ''terms'' length(L) and length(L1) without interpreting them, i.e. without calling any predicates. To compare lengths, do

length(L, N), length(L1, N)

If you fix that, your program should be closer to working.

回答4:

I like Sergey's solution for its elegance and simplicity (+1). Here's another approach which is less elegant in favor of some further efficiency as it prunes the cases where append is queried. If either A or B are ground, then we let their length drive the process. Otherwise, we let the length of L drive it:

div(L, A, B) :-
    (   \+ground(A),
        \+ground(B)
    ->  length(L, N),
        HalfN is N div 2
    ;   true
    ),
    length(A, HalfN),
    length(B, HalfN),
    append(A, B, L).

And this will yield, for example:

| ?-  div2(L, A, B).

A = []
B = []
L = [] ? ;

A = [C]
B = [D]
L = [C,D] ? ;

A = [C,D]
B = [E,F]
L = [C,D,E,F] ?
...

| ?- div([1,2,3|T], A, B).

A = [1,2]
B = [3,C]
T = [C] ? ;

A = [1,2,3]
B = [C,D,E]
T = [C,D,E] ? ;
...

| ?- div(L, [1,2], B).

B = [A,C]
L = [1,2,A,C]

yes
| ?- div([1,2|T], [1,2], [3,4]).

T = [3,4]

yes
| ?-

Etc.

回答5:

It would just be,

div(L,L1,L2) :- length(L,Len), N is Len/2, split(L,L1,L2,N).
split([H|T],[H|L1],L2,N):- N1 is N-1, split(T,L1,L2,N1).
split(T,[],T,0).

回答6:

div(L, A, B) :-
append(A, B, L),
length(A, O),
length(B, N),
((O-1)=:=N;(O+1)=:=N;O=:=N),
!.

It's just this, works with odd lenght :)