Finding a pattern in a list, prolog

Question

I´m trying to build a predicate pattern(List,Pattern) that takes a List formed only by a repeated pattern and the output has to be that pattern. Some examples of the List:

List1=[a,b,a,b]
List2=[1,2,3,1,2,3]
List3=[a,a,a,a,a,a,a,a]

As you can see, in each case either the list and the pattern can have different lenghts. And the output in each case would be:

Pattern1=[a,b]
Pattern2=[1,2,3]
Pattern3=[a]

The only way I can think about a solution is taking the first element of the List (for example, in List2 would be "1") and going through List2 until I find again a "1" and then put in Pattern everything before the second 1 ("123"), but I don´t think it is the best solution. Does anybody know an easier way to solve it? Maybe with Append/3 or Member/2? Thank you!

David Tonhofer David Tonhofer · Accepted Answer · 2021-05-16T21:56:20

You are looking for the shortest sequence Q ("pattern") such that list L is n > 0 concatenations of Q (whereby if n = 1 iff Q = L), then

If you have a verifying predicate which verifies that L is indeed a concatenation of a (non necessarily) shortest Q:

multiple_concatenations(X,X).         % L = 1 * Q
multiple_concatenations(Q,L) :-       % L = N * Q (for some N >= 1, Q <> []) if
   concatenation(Q,Rest,L),           % L = Q + Rest and                                       
   multiple_concatenations(Q,Rest).   % Rest = M * Q  (for some M)

Where concatenation/3 is just the sanely named append/3 from Prolog:

concatenation(List1,List2,List12) :-
   append(List1,List2,List12).

... then you can try to find a shortest Q by just generating longer and longer potential _Q_s (of length going from 1 to length(L)) and break off at the first Q which passes multiple_concatenations(Q,L,N):

shortest_q(Q,L) :-
   length(L,Length),                 % The length of L
   must_be(positive_integer,Length), % Enforce length(L) > 0; throws if not
   length(Q,N),                      % Generate a longer and longer
                                     % "list template" Q (i.e. a list with only
                                     % uninstantiated variables) on backtracking,
                                     % with N = 0,1,2,3,...
   N>0,                              % Don't want an empty template though
   (concatenation(Q,_,L)             % Q's uninstantiated members are
                                     % now instantiated; if this fails,
    ->
    (multiple_concatenations(Q,L),   % Check whether Q is acceptable
     !)                              % If yes, cut (i.e. break off at first answer)
    ;
    fail).                           % If concatenation(Q,_,L) fails, fail the
                                     % predicate: we have
                                     % gone too far (Q is longer than L)

Add a few plunit test cases, which are doubleplus important in the "what am I computing right now?" Prolog wonderland:

:- begin_tests(mq).

test(1) :-
   shortest_q(Q,[a,b,a,b]),
   assertion(Q == [a,b]).

test(2) :-
   shortest_q(Q,[1,2,3,1,2,3]),
   assertion(Q == [1,2,3]).

test(3) :-
   shortest_q(Q,[a,a,a,a,a,a,a,a]),
   assertion(Q == [a]).

test(4) :-
   shortest_q(Q,[a,b,c,d,e,f,g]),
   assertion(Q == [a,b,c,d,e,f,g]).

:- end_tests(mq).

And so:

?- run_tests.
% PL-Unit: mq .... done
% All 4 tests passed
true.

Note however that "verification mode" accepts a sequence longer than the minimum:

?- shortest_q([1,2,3],[1,2,3,1,2,3]).
true.

?- shortest_q([1,2,3,1,2,3],[1,2,3,1,2,3]).
true.

Finding a pattern in a list, prolog

2 Answers