Comment cela se calcule-t-il? J'essaie de comprendre comment les valeurs de H sont assignées dans la liste

Question

Ce prédicat devrait imprimer une liste de taille N contenant des permutations possibles de 0 et 1.

Ma question est la suivante: la valeur de H est-elle reportée à chaque récursion ou la création de la liste avec les valeurs bit(H) a-t-elle lieu dans la phase de retour arrière?

bit(0). 
bit(1). 
gen(0,[]). 
gen(N,[H|T]) :- 
    N > 0, 
    bit(H), 
    N1 is N - 1, 
    gen(N1,T). 

Answer 1

L'exécution de Prolog est une question de choix. Ici, un point de choix est laissé à chaque étape de récurrence par le prédicat bit/1. Lorsque vous demandez à Prolog de vous fournir une autre solution, elle revient simplement au point de choix le plus jeune. Ici, au lieu de passer par la première clause de bit/1 et de lier H à 0, il passera par la deuxième clause et liera H à 1. Une fois que les deux clauses ont été choisies, Prolog reviendra à un point de choix plus ancien, etc ... jusqu'à ce que finalement tous les points de choix soient épuisés et le programme retourne false..

vous pouvez essayer vous-même avec le trace/0 prédicat:

?- trace, gen(3, Result). 

Answer 2

Puis-je vous offrir une définition en avant plus droite d'abord:

gen(N, Xs) :- 
    length(Xs, N), 
    maplist(between(0,1), Xs). 

Dans cette définition toutes les parties récursives sont désormais cachés dans certains built-ins. Le premier objectif garantit que Xs est une liste de longueur N. Et l'objectif suivant en sorte que chaque élément est compris entre 0 et 1. Si vous regardez les réponses, vous vous rendrez compte dans quel ordre les solutions sont énumérées:

 
?- gen(4, Xs). 
Xs = [0,0,0,0] ; 
Xs = [0,0,0,1] ; 
Xs = [0,0,1,0] ; 
Xs = [0,0,1,1] ; 
Xs = [0,1,0,0] ; 
Xs = [0,1,0,1] ; 
Xs = [0,1,1,0] ; ... 

Answer 3

Ce prédicat génère tous les numéros (avec commande) en binaire système bien pour le comprendre, vous devez comprendre prolog backtracking, vous pouvez dessiner un arbre de substitution pour le comprendre