Перечислить по порядку в Прологе

Я пытаюсь «обратить» неупорядоченный обход, превратив неупорядоченный список обратно в BST.

BSTs имеет форму предиката node(Value,Left,Right) или leaf, поэтому пустое дерево — это просто leaf, дерево с одним узлом — node(_,leaf,leaf).

Учитывая предикат enumerate_bst(Elems,Bst), цель состоит в том, чтобы сопоставить Bst со всеми возможностями упорядоченного списка Elems. Например (примечание setof/3):

?- setof(Bst,enumerate_bst([],Bst),Enum).
Enum = [leaf].

?- setof(Bst,enumerate_bst([1,2],Bst),Enum).
Enum = [
    node(1, leaf, node(2, leaf, leaf)),
    node(2, node(1, leaf, leaf), leaf)
].

?- setof(Bst,enumerate_bst([1,2,3],Bst),Enum).
Enum = [
    node(1, leaf, node(2, leaf, node(3, leaf, leaf))),
    node(1, leaf, node(3, node(2, leaf, leaf), leaf)),
    node(2, node(1, leaf, leaf), node(3, leaf, leaf)),
    node(3, node(1, leaf, node(2, leaf, leaf)), leaf),
    node(3, node(2, node(1, leaf, leaf), leaf), leaf)
].

Что я пытался сделать:

У меня уже есть предикат, который сопоставляет данный BST с его порядковым списком:

inorder(leaf,[]).
inorder(node(X,L,R),Elems) :-
  inorder(L,Elems_L),
  inorder(R,Elems_R),
  append(Elems_L,[X],Tmp),
  append(Tmp,Elems_R,Elems).

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

Что я сейчас пытаюсь сделать

Я пытаюсь использовать собственный предикат append/3 в обратном порядке, но не могу полностью решить, как это будет сделано.

Любые идеи о том, как лучше всего это сделать? Спасибо!


binary-search-tree prolog dcg failure-slice
person bli00    schedule 04.05.2017    source источник

Ответы (2)


arrow_upward
5
arrow_downward

В обратном случае ваша программа не завершается. Рассмотреть возможность:

?- inorder(Tree, []).
   Tree = leaf
;  **LOOPS**

Мы ожидаем, что он просто покажет это единственное решение, а затем остановится. Фактическая причина заключается в следующем фрагменте вашей программы - отказ-срез. Нет необходимости смотреть дальше, чем это. Другими словами, вообще не нужно понимать append/3.

?- inorder(Tree, []), false.

inorder(leaf,[]) :- false.
inorder(node(X,L,R),Elems) :-
   inorder(L,Elems_L), false.
   inorder(R,Elems_R),
   append(Elems_L,[X],Tmp),
   append(Tmp,Elems_R,Elems).

Во-первых, этот фрагмент должен завершиться (и потерпеть неудачу). Только тогда вы можете рассмотреть вопрос о прекращении всей программы. В этом фрагменте второй аргумент (Elems) полностью игнорируется! Первая цель, которая его заинтересует, это самая последняя (append(Tmp,Elems_R,Elems)).

Наивным выходом было бы изменить порядок целей, поставив две append/3 цели на первое место. Это работает (то есть завершается для второго аргумента земли), но совершенно неудовлетворительно, так как программа теперь посвящена распределению элементов списка по деревьям только< /эм>.

Вот версия, которая работает в обе стороны, как указано в условии завершения:

inorder(A,B)terminates_if b(A);b(B).

в котором говорится, что inorder/2 завершается, если первый или второй аргумент является заземлением.

inorder(Tree, Xs) :-
   phrase(inorder(Tree, Xs,[]), Xs).

inorder(leaf, Vs,Vs) -->
   [].
inorder(node(X,L,R), [_|Vs0],Vs) -->
   inorder(L, Vs0,Vs1),
   [X],
   inorder(R, Vs1,Vs).
person false    schedule 04.05.2017
comment
Каков синтаксис --> в этом случае? - person bli00; 04.05.2017
comment
Это dcg. Произнесите listing(inorder), чтобы увидеть, как оно расширяется до обычного предиката Пролога. - person false; 04.05.2017

arrow_upward
1
arrow_downward

Некоторое время назад я написал 'библиотеку' для этой задачи. . Используя это:

:- use_module(carlo(snippets/when_)).

inorder(leaf,[]).
inorder(node(X,L,R),Elems) -:-
  inorder(L,Elems_L),
  inorder(R,Elems_R),
  append(Elems_L,[X],Tmp),
  append(Tmp,Elems_R,Elems).

тогда

?- inorder(T,[1,2,3]).
T = node(1, leaf, node(2, leaf, node(3, leaf, leaf))) ;
T = node(1, leaf, node(3, node(2, leaf, leaf), leaf)) ;
T = node(2, node(1, leaf, leaf), node(3, leaf, leaf)) ;
T = node(3, node(1, leaf, node(2, leaf, leaf)), leaf) ;
T = node(3, node(2, node(1, leaf, leaf), leaf), leaf) ;
false.

Единственное изменение в вашем коде (помимо включения «библиотеки») — это замена :- на -:-. Я выбрал символ, чтобы обозначить двунаправленность...

person CapelliC    schedule 04.05.2017
comment
Создает много несоответствий, например L=[_], T = node(A,node(B,leaf,leaf),leaf), inorder(T, L)., у которого нет решения, и, следовательно, он скорее потерпит неудачу. - person false; 04.05.2017