Rechercher des répétitions dans une liste

Question

Comment rechercher une répétition consécutive d'une chaîne dans une liste dans prolog?

Ce que je suis exactement essayer de trouver, par exemple, est la suivante:

input => output 
AAAAAA => 6*(A) 
ABABAB => 3*(AB) 
ABCABCABC => 3*(ABC) 

j'ai écrit une grammaire DCG pour cela et je suis en train de le faire me donner cette suite.

est ici la grammaire, si nécessaire:

exp --> term. 
exp --> term, [+], exp. 

term --> factor. 
term --> digit, [*], exp. 

factor --> elem. 
factor --> ['S'], ['['], sym, [']']. %S[(A)(B),(C)] 
factor --> ['<'], alt, ['>'], ['/'], ['<'], alt, ['>']. %<(A)>/<(B)(C)(D)> 
factor --> ['('], exp, [')']. 

sym --> factor. 
sym --> factor, [','], factor. 
sym --> factor, sym. 

alt --> factor. 
alt --> factor, alt. 

elem --> char. 
elem --> char, elem. 
char --> [D], {is_alnum(D)}. 
digit --> [D], {is_alnum(D)}. 
digit --> [D], {number(D)}. 

nbr_to_char(N, Cs) :- 
    name(Cs, [N]). 
str_to_list(S, Cs) :- 
    name(S, Xs), 
    maplist(nbr_to_char, Xs, Cs). 

eval(L) :- 
    str_to_list(L, X), 
exp(X, []). 

Merci pour toute aide.

Answer 1

Je pense que ce que vous recherchez est pack (dcg_util). Mais aussi considérer ajouter/2:

?- A=`ababab`. 
A = [97, 98, 97, 98, 97, 98]. 

?- append([X,X,X],$A). 
X = [97, 98], 
A = [97, 98, 97, 98, 97, 98] ; 
false. 

Maintenant, si nous venons de trouver un moyen facile de faire des listes de variables répétées, nous avons une construction assez puissant, nous pouvons utiliser pour faire face à un problème. Essayons:

?- length(L,3),maplist(=(X),L). 
L = [X, X, X]. 

Alors:

?- length(L,_),maplist(=(X),L),append(L,$A). 
L = [[97, 98, 97, 98, 97, 98]], 
X = A, A = [97, 98, 97, 98, 97, 98] ; 
L = [[97, 98], [97, 98], [97, 98]], 
X = [97, 98], 
A = [97, 98, 97, 98, 97, 98] ; 
^CAction (h for help) ? abort 
% Execution Aborted 

oups, histoire sans fin ... mais un peu ennuyeux. Besoin d'un peu plus de code, l'application de la connaissance du domaine (ensachage, vraiment ...)

?- length($A,U),between(1,U,N),length(L,N),maplist(=(X),L),append(L,$A). 
U = 6, 
N = 1, 
L = [[97, 98, 97, 98, 97, 98]], 
X = A, A = A, A = [97, 98, 97, 98, 97, 98] ; 
U = 6, 
N = 3, 
L = [[97, 98], [97, 98], [97, 98]], 
X = [97, 98], 
A = A, A = [97, 98, 97, 98, 97, 98] ; 
false.