Пролог для начинающих: как создать уникальные значения для каждой переменной в предикате

Question

У меня есть предикат пролога:

Add( [A|B] , Answer ) :-
    ...
    ~ Add everything in the list to come up with answer
    ...

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

---

Вот что-то, что логически эквивалентно:

?- AddUnique([A, B, C], 10). эквивалентно: ?- Add([A, B, C], 10), A != B, B != C, A != C.

А также:

?- AddUnique([A, B, B], 10). эквивалентно: ?- Add([A, B, B], 10), A != B.

Также:

?- AddUnique([A, B, B], 10). НЕ эквивалентно: ?- Add([A, B, B], 10), A != B, B!=B.

---

Если ?- AddUnique([A,B,C,D], 4). дается, что он должен возвращать false, поскольку он не может содержать уникальные положительные целые числа, которые добавляют к четырем.

Если ?- AddUnique([A,A,A,A], 4). дано должно вернуться A=1,

---

Вопрос: Как мне переместить A != B, B != C, A != C. логика внутри предиката, не делая что-то подобное A != A?

Answer 1

Это решение, которое я придумал. Он будет назначать входные данные только числам меньше десяти, но отлично работает для этого!

addUnique( A, Answer ) :- 
    used(A,[0,1,2,3,4,5,6,7,8,9],_),
    add(A,Answer).

add( [A|B] , Answer ) :-
    ~ Add everything in the list to come up with answer ~.


% ================================
% Ensures that all variables are unique.  
% ================================

% Base case: Assigned variables unique values
used([], Nin, Nin).

% Have already assigned a value to this variable
used([A|B], Nin, Nout) :-
        integer(A),
        helper(B,Nin,Nout).

% Have not assigned a value to this variable yet
% Assign it and remove it from the list.  
used( [A|B] , Nin, Nout) :-
        member(A,Nin),
        delete(Nin,A,Temp),
        helper(B,Temp,Nout).

Answer 2

Хм... Вы должны это понимать doStuff(A,B,C,D) а также doStuff(A,A,B,B) средства. Сначала будет унифицировать ценности A.. D с соответствующими значениями, которые делают doStuff/4 достижимая цель. И второе равно A=B, C=D, doStuff(A,B,C,D) а также doStuff(A,B,C,D), A=B, C=D (но последний вариант, вероятно, вызовет возврат). Надеюсь, вы понимаете, что unique/1 не должно быть сделано внутри doStuff/4потому что это вне ограничения. Так что вы должны использовать doStuff(A,B,C,D), unique([A,B,C,D]) а также doStuff(A,A,B,B), unique([A,B]),

Интересно как ты читаешь A is not B... В любом случае вы можете определить unique/1 как

not_unique([H|T]):- member(H, T) ; not_unique(T).
unique(L):- not(not_unique(L)).

Answer 3

Учитывая ваше описание addUnique/2 Предикат, программирование логики ограничений может быть использовано для реализации решения. Это далеко не новичок, но я все равно выложу объяснение.

Во-первых, возможно, стоит посмотреть, что такое программирование логики ограничений и как использовать реализацию (например, SWI-PL clpfd). По сути, программирование логики ограничений (в частности, решатель конечных областей) позволит вам указать следующие ограничения для ваших переменных в списке ввода: addUnique/2:

1. Как переменные в вашем входном списке могут связываться с определенными числовыми значениями (т. Е. Целыми числами от 0 до и включая указанное значение)
2. Как разные переменные в вашем входном списке не могут одновременно связываться с одним и тем же значением (т. Е.!= Где разные)
3. Как сумма переменных во входном списке плюс любые числа должны складываться до заданного значения (т. Е. Максимального значения, которое переменные могут принимать в 1, выше).

Вместе эти спецификации позволят основному анализатору ограничений автоматически определять, какие допустимые значения могут одновременно принимать переменные с учетом вышеуказанных ограничений, предоставляя вам ваши решения (их может быть несколько, один или ни одного).

Вот решение с использованием вышеупомянутого решателя ограничений в SWI-PROLOG (решатель clpfd):

:- use_module(library(clpfd)).  % import and use the constraint solver library

addUnique([A|As], Val) :-
    unique_vars([A|As], UVs),  % determine all unique variables
    UVs ins 0..Val,            % (1) domain of all unique variables is 0 to Val
    pairwise_inequ(UVs),       % (2) all unique variables are pairwise !=
    construct_sum_constr(As, Val, A, Program),  % (3) construct the sum constraint
    Program,              % assert the sum constraint
    label(UVs).           % label domains to enumerate a solution (backtracks)

% predicate to return a list of unique vars, if present
unique_vars([], []).
unique_vars([V|Vs], [V|Uniq]) :-
    var(V),
    \+ var_memberchk(V, Vs), !,
    unique_vars(Vs, Uniq).
unique_vars([_|Vs], Uniq) :-
    unique_vars(Vs, Uniq).

% predicate to test if a variable appears in a list (possibly including variables)
var_memberchk(V0, [V1|_]) :- 
    V0 == V1, !.
var_memberchk(V0, [_|V1s]) :- 
    var_memberchk(V0, V1s).

% create constraints that assert each in the input list != to each other
pairwise_inequ([]).
pairwise_inequ([V|Vs]) :-
    map_inequ(Vs, V),
    pairwise_inequ(Vs).

% predicate to pairwise assert inequality between all list members
map_inequ([], _).
map_inequ([V1|V1s], V0) :-
    V0 #\= V1,   % the inequality constraint
    map_inequ(V1s, V0).

% predicate to construct a summation constraint, whereby all variables in the 
% input list are constructed into a sum with +/2 and finally equated to a value
construct_sum_constr([], Val, Sum, (Sum #= Val)).
construct_sum_constr([V|Vs], Val, Sum, Program) :-
    construct_sum_constr(Vs, Val, (V + Sum), Program).

Запуск этого кода, например, дает вам:

?- addUnique([A,B,B], 6).
A = 0,
B = 3 ;
A = 4,
B = 1 ;
A = 6,
B = 0.

; перечисляет следующее решение для допустимых привязок между переменными. Обратите внимание, что A а также B никогда не принимать одно и то же значение, как требуется, но все вхождения в списке ввода всегда будут суммироваться в 6, Еще один запрос:

 ?- addUnique([A,A,A],4).
false.

Результатом является ошибка здесь, потому что не может быть найдено единственное целое число, связывающее с A что при подведении итогов составило 4, в то время как:

 ?- addUnique([A,A,A,A],4).
A = 1.

...как и ожидалось. Кроме того, вы хотели попробовать:

?- addUnique([A,B,C,D],4).
false.

Опять же, результатом здесь является сбой, потому что все переменные A, B, C а также D все были утверждены, чтобы быть разными, и не могут все связать 1,

РЕДАКТИРОВАТЬ пс. Они тоже хотели попробовать:

?- addUnique([A,A,A,1],4).
A = 1.

Простая модификация приведенного выше кода гарантирует, что при вызове используются только переменные ins утверждать домены (а не любые цифры в списке ввода).