Как предотвратить дублирование в сгенерированных последовательностях с помощью dif/2?

Question

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

Как правильно заметил Борис в комментариях, существует множество существующих решений этой проблемы. Однако меня интересует решение, в котором не используется аккумулятор (т. Е. Список уже выбранных элементов, с которым сравнивается вновь выбранный элемент), но в котором используется dif/2 заявления вместо.

Для иллюстрации, в моей следующей программе у меня есть 4 элемента и, после 4 рекурсивных вызовов, пара div/2 утверждения, которые утверждают, что 4 элемента, которые были выбраны до сих пор, являются парами разнородными. Из этого можно сделать вывод, что нет смысла продолжать рекурсию и искать пятый элемент, так как не осталось элементов с учетом div/2 заявления. Есть ли способ закодировать это "знание" в программу, чтобы она больше не зацикливалась?

:- use_module(library(apply)).
:- use_module(library(dif)).

sequences([]).
sequences([H|T]):-
  maplist(dif(H), T),
  between(1, 4, H),
  sequences(T).

Текущее, зацикленное поведение:

?- sequences(X).
X = [] ;
X = [1] ;
...
X = [4, 3, 1, 2] ;
X = [4, 3, 2, 1] ;
<LOOP>

Answer 1

^{Крошечный вопрос для начала - название:} sequences/1 ^{предлагает список последовательностей (какой бы ни была последовательность), это должно быть довольно} sequence/1 ^,

Вы требуете много плохой системы Пролога: вы требуете большей последовательности. Я полагаю, любой ценой.

Моя немедленная реакция (использовать library(clpfd)!) не работает, посмотрим почему

?- length(Xs,N),Xs ins 1..4, all_distinct(Xs).

Он зацикливается так же, как и ваша версия, что лучше всего видно по этому фрагменту ошибки:

? - длина (Xs, N), false, Xs ins 1..4, all_distinct (Xs).

Так уже length/2 один не так. Возможно, я повторяю вашу программу и пытаюсь определить, почему ваша программа не прекращает работу:

последовательности ([]):- ложно.
последовательности ([H|T]):-
  список карт (dif(H), T), ложь
  между (1, 4, Н),
  последовательности (T).? - последовательности (X), ложь.

Наш дорогой декларативный плакат ребенка maplist/2 поймали во флагранти! ОК, может быть, мы не должны быть такими резкими. В конце концов, честное недопущение предиката всегда предпочтительнее недобросовестно необоснованного или неполного взлома.

Нам нужно понять, что all_distinct/1 требует, чтобы длина списка была известна, и все домены также должны присутствовать.

sequence(Xs) :-
   sequence_aux(Xs, []).

sequence_aux([], _).
sequence_aux([X|Xs], Ys) :-
   X in 1..4,
   all_distinct([X|Ys]),
   sequence_aux(Xs, [X|Ys]).

 ?- sequence(X). 

Теперь заканчивается.

@mat может заметить, что all_distinct([_]) может быть удален. Может быть, даже больше, чем это.

Если вам не нравится это решение, потому что оно использует дополнительный аргумент, вам нужно будет реализовать более безопасный maplist/2,

fmaplist(C_1, Xs) :-
    freeze(Xs, fmaplist_aux(C_1, Xs)).

fmaplist_aux(_C_1, []).
fmaplist_aux(C_1, [X|Xs]) :-
   call(C_1, X),
   freeze(Xs, fmaplist_aux(C_1, Xs)).

Теперь вы можете использовать свою оригинальную программу дословно. Но я не очень хорошо себя чувствую. Понять точные границы отсутствия завершения в программе с заморозкой гораздо сложнее.

---

Кроме того: вы можете попытаться получить правильные имена переменных в SWI для замены ответов, потому что _G772 Подобная нумерация не позволяет повторно вставить ответ обратно в оболочку верхнего уровня и получить правильные результаты.

Answer 2

Не настоящий ответ, но слишком длинный для комментария:

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

РЕДАКТИРОВАТЬ:

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

Не использовать dif/2потому что это не обязательно. Вместо этого, например:

combination([], _).
combination([X|Xs], Set) :-
    select(X, Set, Set0),
    combination(Xs, Set0).

Здесь вы должны построить свой начальный набор, используя setof/3или другой предикат, который составляет список всех решений. Я не вижу необходимости в dif/2 если вы можете использовать список и select/3 от него.

Но если вы действительно настаиваете, я бы сделал это так:

set_el(a).
set_el(b).
set_el(c).

set_el_combination(Combination) :-
    set_el_combination_1([], Combination).

set_el_combination_1(C, R) :-
    reverse(C, R).
set_el_combination_1(C0, C) :-
    maplist(dif(X), C0),
    set_el(X),
    set_el_combination_1([X|C0], C).

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

Это помогает вообще?