Prolog - trouver toutes les combinaisons (le produit) de la liste des listes (des listes)

Question

I'v a essayé quelques fonctionnalités à mettre en œuvre un prédicat qui trouve toutes les combinaisons, comme dans cet exemple:

List = [[1, 2], [1, 2, 3]] 

Ces devrait être la sortie,

Comb = [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3]] 

mais toutes les solutions que j'ai trouvé utilisaient findall que je ne veux pas utiliser dans ma tâche.

Comment puis-je différemment implémenter le prédicat, en évitant findall?

Ou peut-être comment puis-je implémenter my_findall sans utiliser de fonctionnalités intégrées?

A solution like here, without built-in predicates would be great

Merci aux aides!

Answer 1

Je ne suis pas sûr que ce soit l'approche la plus efficace, mais il est assez transparent. L'idée ici est de définir le problème dans récursifs (ou inductif) « couches »:

% multiply_lists(ListOfLists, MultipliedListOfLists) 
% 
% The first two clauses handle the case where ListOfLists consists 
% of just one list 
% The third clause handles the general case 
% 
multiply_lists([[X]], [[X]]). 
multiply_lists([[X|Xs]], [[X]|T]) :- 
    multiply_lists([Xs], T). 
multiply_lists([E|Es], R) :- 
    multiply_lists(Es, R1), 
    multiply_list(E, R1, R). 

% multiply_list relates the product of a list of lists and a single list 
% of elements 
% 
multiply_list([], _, []). 
multiply_list([E|Es], L, Ls) :- 
    multiply_list(Es, L, LL), 
    multiply_element(E, L, LL, Ls). 

% multiply_element relates the product, prepended to a given list, 
% of a single list of lists and a single element 
% 
multiply_element(_, [], A, A). 
multiply_element(X, [Y|Ys], A, [[X|Y]|T]) :- 
    multiply_element(X, Ys, A, T). 

multiply_element/4 combine en fait deux règles en une seule: elle définit la multiplication d'une liste par un seul élément, et prepends ces résultats comme personne éléments à une liste donnée.

Un résultat de l'échantillon:

| ?- multiply_lists([[1, 2], [1, 2, 3]], L). 

L = [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3]] ? ; 

no 
| ?- multiply_lists([[a,b,c], [1,2], [x,y]], L). 

L = [[a,1,x],[a,1,y],[a,2,x],[a,2,y],[b,1,x],[b,1,y],[b,2,x],[b,2,y],[c,1,x],[c,1,y],[c,2,x],[c,2,y]] ? ; 

no 

Quelques bizarreries avec la mise en œuvre ci-dessus:

• Ce n'est pas la queue récursif (donc utilisera plus pile que les listes sont plus)
• Il laisse une point de choix

Mais cela illustre bien comment le problème peut être résolu ut en utilisant append/3 ou d'autres prédicats prédéfinis basés sur une liste.

Answer 2

Vous pouvez utiliser l'implémentation de findall de "The Craft of Prolog". Mais de toute façon, vous finirez par utiliser des méta-prédicats intégrés.

donc au sujet de votre linked solution

try([],[]). 
try([L|Ls],[M|Ms]):- 
    member(M,L), 
    try(Ls,Ms). 

findall2(Template, Enumerator, List) :- 
    asserta('find all'([])), 
    call(Enumerator), 
    asserta('find all'({Template})), 
    fail 
; 
    all_found([], List). 


all_found(SoFar, List) :- 
    retract('find all'(Item)), 
    !, 
    /* to stop retract looking for more Items. */ 
    all_found(Item, SoFar, List). 


all_found([], List, List). 

all_found({Template}, SoFar, List) :- 
    all_found([Template|SoFar], List). 

Vous obtiendrez

?- List = [[1, 2], [1, 2, 3]], findall2(M,try(List,M),Comb). 
List = [[1, 2], [1, 2, 3]], 
Comb = [[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3]].