CODEWITHSUNDEEP
prolog
ticica7055
ticica7055

Reputation: 11

Sublist from list

Ieed to select a sublist from the list, from K to N indexes.

Example:

?- sublist(2, 5, [1, 2, 3, 4, 5, 6, 7, 8, 9], Res)
Res = [2, 3, 4, 5]

Upvotes: 1

Views: 252

Answers (3)

brebs
brebs

Reputation: 4456

sublist(StartPos, EndPos, Lst, SubLst) :-
    % Check for sensible inputs
    must_be(integer, StartPos),
    must_be(integer, EndPos),
    StartPos >= 1,
    EndPos >= StartPos,
    % Loop through the list
    sublist_(Lst, StartPos, EndPos, 1, SubLst).


sublist_(Lst, StartPos, EndPos, StartPos, SubLst) :-
    !,
    % At start of sublist
    sublist_within_(Lst, StartPos, EndPos, StartPos, SubLst).

sublist_(Lst, StartPos, EndPos, Pos, SubLst) :-
    % Otherwise, is before the start of the sublist
    Pos1 is Pos + 1,
    % Don't care about the current element in the list
    Lst = [_|Tail],
    sublist_(Tail, StartPos, EndPos, Pos1, SubLst).


sublist_within_(Lst, StartPos, EndPos, Pos, SoFar) :-
    Pos < EndPos,
    % Within the sublist
    !,
    Pos1 is Pos + 1,
    % Remember the current element in the list (in the correct order)
    Lst = [Head|Tail],
    SoFar = [Head|SubLst],
    sublist_within_(Tail, StartPos, EndPos, Pos1, SubLst).

% End of the sublist - instantiate the end of SubLst
sublist_within_([Head|_], _StartPos, EndPos, EndPos, [Head]).

Result in swi-prolog:

?- time(sublist(2, 5, [1, 2, 3, 4, 5, 6, 7, 8, 9], Res)).
% 17 inferences, 0.000 CPU in 0.000 seconds (91% CPU, 514388 Lips)
Res = [2,3,4,5].

A smaller but slower alternative is:

sublist_slow(StartPos, EndPos, Lst, SubLst) :-
    succ(BeforeLen, StartPos),
    SubLstLen is EndPos - StartPos + 1,
    length(BeforeLst, BeforeLen),
    length(SubLst, SubLstLen),
    % append is slow because it needs to iterate through the entire list
    append([BeforeLst, SubLst, _AfterLst], Lst),
    % Don't look for other potentials for _AfterLst
    !.

But the "append" method has the disadvantage of having to iterate through the rest of the list, whereas the first method can stop at the end of SubLst - performance comparison:

test_sublists :-
    numlist(1, 1000000, NL),
    time(sublist(2, 5, NL, _)),
    time(sublist_slow(2, 5, NL, _)).

Result in swi-prolog:

?- test_sublists.
% 17 inferences, 0.000 CPU in 0.000 seconds (90% CPU, 460256 Lips)
% 2,000,015 inferences, 0.249 CPU in 0.247 seconds (101% CPU, 8016137 Lips)

gusbro's method is in the middle, performance-wise:

test_sublists2 :-
    numlist(1, 1000000, NL),
    I = 100000,
    time(sublist(I, I, NL, _)),
    time(sublist_gusbro(I, I, NL, _)),
    time(sublist_slow(I, I, NL, _)).

Performance result:

?- test_sublists2.
% 100,009 inferences, 0.011 CPU in 0.011 seconds (100% CPU, 8970530 Lips)
% 200,009 inferences, 0.015 CPU in 0.015 seconds (100% CPU, 13718721 Lips)
% 1,900,020 inferences, 0.198 CPU in 0.196 seconds (101% CPU, 9585032 Lips)

Here is a variant of Evgeny's code, with improved performance and termination:

sublist_evgeny(St, En, [_ | T], SubT) :-
    St > 1, !,
    % Move closer to the start element
    St0 is St - 1,
    En0 is En - 1,
    sublist_evgeny(St0, En0, T, SubT).

sublist_evgeny(1, 0, _, SL) :-
    !,
    % Finished - the remaining sublist will be empty
    SL = [].

sublist_evgeny(1, En, [H | T], [H | SubT]) :-
    % Populate the sublist
    En0 is En - 1,
    sublist_evgeny(1, En0, T, SubT).

Performance is great:

% 200,001 inferences, 0.010 CPU in 0.010 seconds (100% CPU, 19344211 Lips)

Upvotes: 1

Evgeny
Evgeny

Reputation: 3274

Here is solution without any library functions:

sublist(1, 0, _, []).

sublist(A, B, [H | T], [H | SubT]) :-
  A = 1,
  B1 is B - 1,
  sublist(A, B1, T, SubT).

sublist(A, B, [_ | T], SubT) :-
  A > 1,
  A1 is A - 1,
  B1 is B - 1,
  sublist(A1, B1, T, SubT).

Upvotes: 0

gusbro
gusbro

Reputation: 22585

Given both integers K and N, you may use length/2 and append/3:

sublist(K, N, L, SL):-
  N >= K,
  length(L1, N),       % L1 is a list with N elements
  length([_|L2], K),   % and L2 has K-1 elements.
  append(L2, SL, L1),  % Therefore SL has the last N-K+1 elements of L1
  append(L1, _, L).    % and L starts with L1 and may have some other elements after

Sample run:

?- sublist(2, 5, [1, 2, 3, 4, 5, 6, 7, 8, 9], Res).
Res = [2, 3, 4, 5].

Upvotes: 2

Related Questions