Пролог, убери повторяющиеся результаты в генерации

Question

Я написал прологическую программу, которая генерирует все возможные положения элементов в двумерной таблице.Количество элементов и размер таблицы указаны.

Мой код:

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)).

(там TSize - это размер таблицы, N - это количество элементов,и последний является результатом) Предикат geni генерирует число X в интервале [A;B].

Пример (2 элемента в таблице 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.

Моя таблицашахматная доска и элементы рыцари.В этом случае все элементы равны, но моя программа «думает», что они разные.Как избежать равных результатов?Как это:

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

Answer 1

В настоящее время вы используете not(member(...)), чтобы убедиться, что результат не содержит дубликатов. Чтобы избежать перестановок результата, нужно просто упорядочить элементы в результате.

Шаг 1 - определить порядок, например:

% 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).

Теперь вы должны убедиться, что элемент, который вы хотите добавить в список, «больше», чем все остальные элементы.

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).

Я использую встроенный предикат maplist, чтобы проверить все элементы списка. Из примера должно быть понятно, как это работает.

Если вы хотите изменить порядок, используйте вместо этого «более низкий».

?- 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.