пролог: подмножества длины k - PullRequest
Новая
       10

пролог: подмножества длины k

3 голосов
/ 04 апреля 2011

в классе мы прошли предикат subset_of / 2, который дал мой учитель следующим образом: 

subset_of([],[]).
subset_of([X|Xs],Zs):-subset_of(Xs,Ys),maybe_add(X,Ys,Zs).

maybe_add(_,Ys,Ys).
maybe_add(X,Ys,[X|Ys]).

subsets_of(Xs,Xss):-findall(Ys,subset_of(Xs,Ys),Xss).

Затем он попросил нас изменить его так, чтобы он давал только подмножества некоторой длины K (но не с использованием length / 2, напрямую находя рекурсивное определение). Моя первая попытка состояла в том, чтобы разделить вызов subset_of на один, который добавляет дополнительный элемент, и на тот, который не имеет (вместо вызова Maybe_add), и отслеживать длину переданного списка и проверять в конце, это не сработало, как планировалось вообще. 

subset_of(K, 0, [],[]).
subset_of(K, Len, [X|Xs],Zs):-
        L1 is Len - 1,
        subset_of(K, L1, Xs, Zs),
        L1 == K.
subset_of(K, Len, [X|Xs],Zs):-
        L1 is Len - 1,
        subset_of(K, L1, Xs,Ys),
        do_add(X, Ys, Zs),
        Len == K.
subsets_of(K,Xs,Xss):-
        length(Xs, Len),
        findall(Ys,subset_of(K, Len, Xs,Ys),Xss).

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

Ответы [ 2 ]

1 голос
/ 04 апреля 2011

Если вам не нужен прямой ответ, чем я бы сказал, что это можно сделать гораздо проще.У меня есть 3 правила в моем решении.Тем не менее, я не использую эту дополнительную формулу maybe_add или что-то, что ее переименовывает.Если вам это действительно нужно, его можно использовать, и тогда он принимает 5 аргументов - 3 входных аргумента и 2 выходных аргумента.Это уменьшает количество правил для subset_of до 2, как в исходном решении.В конце концов, они очень похожи.

Также следите за повторениями.Я думаю, что subset_of(0, _, []), как предлагается в другом ответе, может привести к повторениям.Однако может быть правильное решение, которое включает его, я не уверен, что нет.

Думайте об этом как о подтверждении правильности.Скажем, вы хотели рекурсивно доказать, что один набор является подмножеством K-элемента другого.Как бы вы пошли об этом.Посмотрите на последствия, которые вы использовали.Как вы можете превратить их в правила Пролога?

0 голосов
/ 04 апреля 2011

Не использовать maybe_add кажется хорошей идеей. Однако вам не нужны два дополнительных аргумента: один подойдет. Ваше базовое предложение будет 

subset_of(0, _, []).

т. Е. Пустой набор - это подмножество нулевого элемента чего-либо. Из двух рекурсивных предложений один будет искать подмножества K-1 -элементов, а другой - подмножества K.

...