Предикат дает список несвязанных переменных вместо всех возможных списков - PullRequest
Новая
       14

Предикат дает список несвязанных переменных вместо всех возможных списков

0 голосов
/ 09 октября 2018

Допустим, у меня есть список L1 = [1,2,3], я хочу написать предикат, который может найти все перестановки в этом списке, т.е. 

[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]

Примечание: я знаю permutation(L1, L2).делает именно это, но я хочу написать свой собственный предикат, который делает это для упражнения.

Я новичок в прологе, поэтому я подумал, что давайте сначала сделаем предикат, который возвращает true, когда два списка L1 и L2 являются перестановками друг друга.Требования для этого:

  1. Они должны быть одинаковой длины
  2. Каждый элемент в L1 должен быть в L2

Итак, я пришелс этим: 

permute(L1,L2):-
    forall(member(X,L1), member(X,L2)), % every element that is a member in L1 has to be a member in L2
    length(L1,A), % the length of the list L1 is A
    length(L2,A). % AND the length of the list L2 is A

Поэтому, когда я запрашиваю permute([1,2,3], [1,3,2])., я получаю true, как и ожидалось, и permute([1,2,3], [1,3]). и permute([1,2,3], [1,3,4]). оба дают false.Так что мой предикат работает, чтобы увидеть, являются ли 2 списка перестановками друг друга.

Но если я спрашиваю: permute([1,2,3], A). Я хочу иметь возможность видеть все действительные А, то есть все перестановки из [1,2,3].Вместо этого я получаю неограниченные переменные.Что-то вроде A = [_942, _948, _954].

Почему это происходит, почему я не могу просмотреть все возможные списки A?Есть ли простой способ изменить мой код, чтобы это произошло?

1 Ответ

0 голосов
/ 09 октября 2018

Прежде всего, ваше определение двух точек неверно.В соответствии с этим, permute( [1,1,2], [1,2,2]) должен содержать (и он имеет).

"простой" способ заключается в использовании select/3, 

select( [A|B], X):- select(A, X, Y), select(B, Y).
select( [], []).

И этоработает, но только в одном направлении.Даже добавление (просто) same_length не помогает: 

permute( A, B):- same_length( A, B), select( B, A).

same_length( A, B):- length(A, N), length(B, N).   % wrong

% permute( [1,2,3], X).    % OK
% permute( X, [1,2,3]).    % doesn't terminate after the last solution

Нет, same_length/2 должно быть определено аккуратно, как 

same_length( [], []).
same_length( [_|A], [_|B]):- same_length(A, B).

Тогда permute в порядке в обоих направлениях.

...