Генератор пролога зависает бесконечно, пытаясь снова и снова ОДИН ОБЪЕКТ?

Question

Я действительно застрял на проблеме в Prolog. Я пытаюсь создать генератор "gen_lists_of_pairs (V, L)", который, учитывая список натуральных чисел V, генерирует все возможные списки, содержащие двухэлементные списки, так что их элементы уникальны, и каждый элемент имеет форму [ A, B], где A и B являются членами V и A Это мой код:

ascending([_]).
ascending([A, B|L]) :- A < B, ascending([B|L]).

gen_list_of_pairs(_, []).

gen_list_of_pairs(V, [[X,Y]|L]) :-
    gen_list_of_pairs(V, L),
    member(X, V),
    member(Y, V),
    ascending([X, Y]),
    not((member([X, Y], L))).

И это трассировка отладки при вызове «gen_list_of_pairs ([1], X).»:

Call:gen_list_of_pairs([1], _7086)
 Exit:gen_list_of_pairs([1], [])
X = []
 Redo:gen_list_of_pairs([1], _7086)
 Call:gen_list_of_pairs([1], _7902)
 Exit:gen_list_of_pairs([1], [])
 Call:lists:member(_7906, [1])
 Exit:lists:member(1, [1])
 Call:lists:member(_7912, [1])
 Exit:lists:member(1, [1])
 Call:ascending([1, 1])
 Call:1<1
 Fail:1<1
 Fail:ascending([1, 1])
 Redo:gen_list_of_pairs([1], _7902)
 Call:gen_list_of_pairs([1], _7920)
 Exit:gen_list_of_pairs([1], [])
 Call:lists:member(_7924, [1])
 Exit:lists:member(1, [1])
 Call:lists:member(_7930, [1])
 Exit:lists:member(1, [1])
 Call:ascending([1, 1])
 Call:1<1
 Fail:1<1
 Fail:ascending([1, 1])
 Redo:gen_list_of_pairs([1], _7920)
 ...

Как видите, после вывода «X = []» пролог застревает в бесконечном l oop, пробуя пару [1,1] снова и снова, даже несмотря на то, что, насколько мне известно, он должен либо попытаться сделать что-то еще, либо остановить запрос после неудачной попытки ... Я вообще не могу понять это происходит, и я становлюсь все более разочарованным. Любая помощь будет принята с благодарностью ...

Answer 1

Там слишком много рекурсии. Тем более, что вы рекурсивно повторяете "слева"

gen_list_of_pairs(V, [[X,Y]|L]) :-
    gen_list_of_pairs(V, L), ...

Если второй аргумент не установлен, это уходит в бесконечность, независимо от того, что будет дальше:

gen_list_of_pairs(V, [[X,Y]|L]) :-
    gen_list_of_pairs(V, L),false.

Затем:

?- gen_list_of_pairs([1,2,3],X).
ERROR: Stack limit (1.0Gb) exceeded

... потому что критерия остановки нет. Мы просто накапливаем [X,Y] в постоянно растущий список.

Лучше начать с sh.

Фактически, задача добавления в «Мешок с решениями» выполняется bagof/3 и setof/3.

Нам просто нужно сгенерировать новые пары с возможностью обратного отсчета из V:

gimme_another_pair(V,[X,Y]) :-
   member(X,V),
   member(Y,V),
   X < Y.

Затем

?- gimme_another_pair([1,2,3],P).
P = [1, 2] ;
P = [1, 3] ;
P = [2, 3] ;
false.

И так:

gen_list_of_pairs(V, Result) :- setof(P,gimme_another_pair(V,P),Result).

И так :

?- gen_list_of_pairs([1,2,3],X).
X = [[1, 2], [1, 3], [2, 3]].