Prolog, supprimer les résultats répétitifs dans la génération

Question

J'ai écrit un programme prologue qui génère toutes les positions possibles des éléments dans une table bidimensionnelle. Le nombre d'éléments et la taille de la table sont donnés.

Mon code est:

geni(Min, Min, Max) :- Min =< Max. 
geni(Min, X, Max) :- Max >= Min, MinInc is Min+1, geni(MinInc, X, Max). 
generate(_, 0, []) :- !. 
generate(TSize, N, [X|Tail]) :- NDec is N-1, generate(TSize,NDec, Tail), 
           X=k(X1,Y1), geni(1,X1,TSize), geni(1,Y1,TSize), 
           not(member(X, Tail)). 

(y TSize est la taille de la table, N est le nombre d'éléments, et le dernier est le résultat) geni prédicat génère nombre dans l'intervalle X[A;B].

Exemple (2 éléments de tableau 2x2):

?- generate(2, 2, R). 
R = [k(1, 1), k(1, 2)] ; 
R = [k(1, 1), k(2, 1)] ; 
R = [k(1, 1), k(2, 2)] ; 
R = [k(1, 2), k(1, 1)] ; 
R = [k(1, 2), k(2, 1)] ; 
R = [k(1, 2), k(2, 2)] ; 
R = [k(2, 1), k(1, 1)] ; 
R = [k(2, 1), k(1, 2)] ; 
R = [k(2, 1), k(2, 2)] ; 
R = [k(2, 2), k(1, 1)] ; 
R = [k(2, 2), k(1, 2)] ; 
R = [k(2, 2), k(2, 1)] ; 
false. 

Ma table est échiquier et les éléments sont chevaliers. Dans ce cas tous les éléments sont égaux mais mon programme "pense" qu'ils sont différents. Comment éviter des résultats égaux? Comme ceci:

R = [k(1, 1), k(1, 2)] ; 
R = [k(1, 2), k(1, 1)] ; 

Answer 1

Actuellement, vous utilisez not(member(...)) pour assurer le résultat ne contient pas de double. Pour éviter d'obtenir toutes les permutations d'un résultat, il suffit de s'assurer que les éléments du résultat sont ordonnés.

Étape 1 est de définir un ordre, à savoir comme ceci:

% A knight 1 is "bigger" than knight 2 
% if the X-value is bigger or X is equal and Y is bigger 
is_bigger(k(X1, Y1), k(X2, Y2)) :- 
    X1 > X2; (X1 = X2, Y1 > Y2). 

Maintenant, vous devez vous assurer que l'élément que vous souhaitez ajouter à la liste est « plus grand » que tous les autres éléments.

geni(Min, X, Max) :- between(Min, Max, X). 
generate(_, 0, []) :- !. 
generate(TSize, N, [X|Tail]) :- X=k(X1,Y1), NDec is N-1, 
          generate(TSize,NDec, Tail), 
          geni(1,X1,TSize), 
          geni(1,Y1,TSize), 
          maplist(is_bigger(X), Tail). 

J'utilise le prédicat de construction en maplist pour tester tous les éléments de la liste. Frome l'exemple, il devrait être clair comment cela fonctionne.

Si vous souhaitez inverser l'ordre, implémentez un "inférieur" à la place.

?- generate(2, 2, T). 
T = [k(1, 2), k(1, 1)] ; 
T = [k(2, 1), k(1, 1)] ; 
T = [k(2, 2), k(1, 1)] ; 
T = [k(2, 1), k(1, 2)] ; 
T = [k(2, 2), k(1, 2)] ; 
T = [k(2, 2), k(2, 1)] ; 
false.