Split a list into two lists of the same length

Question

There is an initial list, split into two lists of the same length (ex. a list of 10 elements, split into 5 elements each), please, can anyone know with explanations desirable. Input: [1,2,3,4,5,6,7,8,9,10] Output: [1,2,3,4,5] [6,7,8,9,10] My beginnings:

len([],0).
len([X|L],N):-len(L,M),N is M+1.
?-len([1,2,3,4,5],X),write(X),nl.

%split([],[],[]).
%split([A],[A],[]).

%split([A|T],[A|T1],[B|T2]):-
%   split(T,T1,T2).

%?-split([1,2,3,4,5,6],Lst1,Lst2),write(Lst1),write(Lst2),nl.

Look at this post https://stackoverflow.com/questions/22995777/splitting-a-list-into-two-lists-equal-in-length-in-prolog/23012757#23012757 (8 years before the other post) — joel76, Oct 16 '22 at 21:20
Do you have any constraints on the "output" lists? Would `List1 = [1,3,5,7,9], List2 = [2,4,6,8,10]` be a reasonable answer, too? — repeat, Oct 17 '22 at 15:53
So would `List1 = [1,3,5,7,9], List2 = [2,4,6,8,10]` be a valid answer? — repeat, Oct 19 '22 at 07:00
I've posted a better solution at https://stackoverflow.com/a/74130437/ which copes with `split_list_half(L, H1, [c]).` — brebs, Oct 19 '22 at 18:49

score 1 · Answer 1 · answered Oct 19 '22 at 19:17

If the list item order doesn't matter to you, you might find the following split/3 congenial.

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

Sample queries using GNU Prolog 1.5.0:

| ?- split([a,b,c,d],Xs,Ys).

Xs = [a,c]
Ys = [b,d]

yes
| ?- split([a,b,c,d,e],Xs,Ys).

Xs = [a,c,e]
Ys = [b,d]

yes

score 0 · Answer 2 · answered Oct 17 '22 at 19:08

If order doesn't matter, then just:

partition( []       , []     , []     ) .
partition( [Y]      , [Y]    , []     ) .
partition( [Y,Z|Xs] , [Y|Ys] , [Z|Zs] ) :- partition(Xs,Ys,Zs) .

If order is important, then the easiest way would be to simply

partition( Xs , Ys , Zs ) :-
  length(Xs,N),    
  M is N div 2,
  length(Ys,M),
  append(Ys,Zs,Xs) .

[Though probably not what your instructor is looking for.]

Something like this would work:

partition( Xs , Ys, Zs ) :-
  length(Xs,N0),
  N is N0 div 2 ,
  partition( N , Xs, Ys, Zs )
  .

partition( 0 ,    Zs  , []     , Zs ) .
partition( N , [X|Xs] , [X|Ys] , Zs ) :- N1 is N-1, partition(N1,Xs,Ys,Zs).

It runs in O(N) time — O(1.5N) actually. It traverses the source list once to determine its length, and then again to partition it.

As would this:

partition( Xs , Ys , Zs ) :- partition(Xs,Xs,Ys,Zs) .

partition( []       ,    Xs  , []     , Xs ) .
partition( [_]      , [X|Xs] , [X|Ys] , Xs ) .
partition( [_,_|Ts] , [X|Xs] , [X|Ys] , Zs ) :- partition(Ts,Xs,Ys,Zs ) .

Here you pass the source list to the helper predicate twice. From the one list, we strip two items on each iteration, and from the other, a single item. Once the list we're stripping two items from it exhausted, we're done.

This runs in O(N) time as well — O(N/2) actually, so it's somewhat more time efficient.

if there is an odd number of digits in the list, it adds an incomprehensible number to the first list, can you please correct it? — Дима Николаев, Oct 19 '22 at 10:00
partition( Xs , Ys , Zs ) :- partition(Xs,Xs,Ys,Zs) . partition( [] , Xs , [] , Xs ) . partition( [_] , [X|Xs] , [X|Ys] , Xs ) . partition( [_,_|Ts] , [X|Xs] , [X|Ys] , Zs ) :- partition(Ts,Xs,Ys,Zs ) . ?-partition([1,2,3,4,5,6,7,8,9,10,11],Lst1,Lst2),write(Lst1),write(Lst2). — Дима Николаев, Oct 19 '22 at 10:00

Split a list into two lists of the same length

2 Answers2