CODEWITHSUNDEEP
listprologsublist
BallOfConfusion
BallOfConfusion

Reputation: 43

Prolog - Find sublists in order

I am currently using this in my Prolog program:

sublist(X, L) :- append(_, S, L), append(X, _, S).

It will correctly list the sublists of a list if I call it like so,

?- sublist(A, [1, 2, 3]).
A = [] ;
A = [1] ;
A = [1, 2] ; 
A = [1, 2, 3] ;
A = [] ;
A = [2] ;
A = [2, 3] ;
A = [] ;
A = [3] ;
A = [] ;
false.

I am looking to make a new function that will try all the shorter substrings first, so that it will come up with something more like

[1] ; [2] ; [3] ; [1, 2] ; [2, 3] ; [1, 2, 3].

Taking out the empty lists isn't vital, but would be preferred.

Upvotes: 2

Views: 2546

Answers (3)

Ans Piter
Ans Piter

Reputation: 573

with Sicstus-prolog it's easy with sublist(?X,+List). inside library(lists3).

code

%   sublist(?Sub, +List)
%   is true when all members of Sub are members of List
:- sublist(?,+) is nondet.
sublist(List, List).
sublist(Sub, [Head|Tail]) :- sublist_(Tail, Head, Sub).

:- sublist_/3 is nondet.
sublist_(Sub, _, Sub).
sublist_([Head|Tail], _, Sub) :- sublist_(Tail, Head, Sub).
sublist_([Head|Tail], X, [X|Sub]) :- sublist_(Tail, Head, Sub).

result 

?- sublist(Y,[1,2,3]).
Y = [1,2,3] ? ;
Y = [2,3] ? ;
Y = [3] ? ;
Y = [] ? ;
Y = [2] ? ;
Y = [1,3] ? ;
Y = [1] ? ;
Y = [1,2] ? ;
no

Upvotes: 0

CapelliC
CapelliC

Reputation: 60004

I swapped arguments order, for readability - please forgive me :)

sublist(L, S) :-
 length(L, N),
 between(1, N, M),
 length(S, M),
 append([_,S,_], L).

yields

?- sublist([a,b,c],S).
S = [a] ;
S = [b] ;
S = [c] ;
S = [a, b] ;
S = [b, c] ;
S = [a, b, c] ;
false.

Upvotes: 1

repeat
repeat

Reputation: 18726

How about one of the following? Using SWI-Prolog we define the following rules:

Version 1

sublist_of([X|Xs], [E|Es]) :-
    append(Ruler, _, [E|Es]),      % ensure we get answers in ascending lengths
    same_length(Ruler, [X|Xs]),
    append([_,[X|Xs],_], [E|Es]).

Version 2

sublist_of__ver2([X|Xs], [E|Es]) :-
    append(Ruler, _, [E|Es]),      % ensure we get answers in ascending lengths
    same_length(Ruler, [X|Xs]),
    append([_,[X|Xs],_], [E|Es]).

Version 3a

sublist_of__ver3a([X|Xs], [E|Es]) :-   
    len1_len2_len12([X|Xs], _, [E|Es]),
    append([_,[X|Xs],_], [E|Es]).

len1_len2_len12([], Ys, Zs) :-
    same_length(Ys, Zs).
len1_len2_len12([_|Xs], Ys, [_|Zs]) :-
    len1_len2_len12(Xs, Ys, Zs).

Version 3b

sublist_of__ver3b(Xs, Es) :-
    Xs = [_|_],
    len1_len2_len12(Xs, _, Es),
    append([_,Xs,_], Es).

Sample query as given by the OP:

?- sublist_of__ver2(Xs, [1,2,3,4]).
   Xs = [1      ]
;  Xs = [  2    ]
;  Xs = [    3  ]
;  Xs = [      4]
;  Xs = [1,2    ]
;  Xs = [  2,3  ]
;  Xs = [    3,4]
;  Xs = [1,2,3  ]
;  Xs = [  2,3,4]
;  Xs = [1,2,3,4]
;  false.

Upvotes: 2

Related Questions