Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Prolog > Список и подсписок

Автор: Coderr 16.11.2010, 09:22

Здравствуйте! Помогите решить задачку или, хотя бы, скажите какие простейшие функции нужны для её решения.

Определите отношение подмножество(Множество, Подмножество), где Множество и Подмножество — два списка, представляющие два множества. Желательно иметь возможность использовать это отношение не только для проверки включения одного множества в другое, но и для порождения вмех возможных подмножеств заданного множества. Например:
?- подмножество([a,b,c], S).
S = [a,b,c];
S = [b,c];
S = [c];
S = [];
S = [a,c];
S = [a];
...

Насколько я понял, функция должна проверять вхождение Подмножества во Множество. Задачу надо сделать на SWI-Prolog.

Поможете?

Автор: Cheloveck 16.11.2010, 10:28

Код


include(Elem, [Elem | _]).

include(Elem, [_ | List]) :-
    include(Elem, List).
    
subset([], List).

subset([X | List1], List2) :-
    subset(List1, List2),
    include(X, List2).

как-то так
PS поправил для решения второй задачи, но генерируемые подмножества с повторениями получаются. Нужно будет их проверить ещё раз include'ом.

Автор: Coderr 16.11.2010, 11:09

Что-то пошло не так... Команда ?- subset([a,b,c],S). возвращает

Код


S = [c, b, a|_G431] ;
S = [c, b, _G430, a|_G434] ;
S = [c, b, _G430, _G433, a|_G437] ;
S = [c, b, _G430, _G433, _G436, a|_G440] ;
S = [c, b, _G430, _G433, _G436, _G439, a|_G443] ;
S = [c, b, _G430, _G433, _G436, _G439, _G442, a|_G446] ;
S = [c, b, _G430, _G433, _G436, _G439, _G442, _G445, a|...] ;
S = [c, b, _G430, _G433, _G436, _G439, _G442, _G445, _G448|...] ;
S = [c, b, _G430, _G433, _G436, _G439, _G442, _G445, _G448|...] ;
S = [c, b, _G430, _G433, _G436, _G439, _G442, _G445, _G448|...] ;
S = [c, b, _G430, _G433, _G436, _G439, _G442, _G445, _G448|...] ;
S = [c, b, _G430, _G433, _G436, _G439, _G442, _G445, _G448|...] ;
S = [c, b, _G430, _G433, _G436, _G439, _G442, _G445, _G448|...] ;
S = [c, b, _G430, _G433, _G436, _G439, _G442, _G445, _G448|...] ;
S = [c, b, _G430, _G433, _G436, _G439, _G442, _G445, _G448|...] ;
S = [c, b, _G430, _G433, _G436, _G439, _G442, _G445, _G448|...] ;
...

Автор: Cheloveck 16.11.2010, 11:12

Цитата(Coderr @ 16.11.2010, 11:09

)

Что-то пошло не так...

тут наоборот надо

Код


?- subset(S,[a,b,c]).

У меня первый параметр - подмножество, а второй - множество.

Автор: Coderr 17.11.2010, 00:06

Действительно, спасибо!
А как сделать, чтобы рекурсия останавливалась? Если я, например, задаю команду ?- subset(S,[a,b,c]), то перебираются все возможные варианты, а потом список продолжается c [a,a,a,a] и до бесконечности.
Такого быть не должно по заданию.

Автор: Coderr 22.11.2010, 22:46

Препод сказал, что это неправильно. Дал подсказку:
«
Есть некие Множество и Подмножество.
Чтобы определить, является ли Подмножество подмножеством Множества, надо последовательно проходить по ним и, если первые их элементы совпадают, отсекать эти первые элементы и продолжать сравнивать оставшиеся списки. Если первые элементы не совпадают, надо отсекать у Множества первый элемент и сравнивать оставшийся список с Подмножеством.
На всякий случай, "отсекать" не значит, что надо использовать отношение "удалить".
»
Попытался сам что-то сделать, но ничего не вышло. В Прологе нет условных выражений и логического ИЛИ (по крайней мере, нам их в теории не дали).
Помогите, пожалуйста.

Автор: Cheloveck 23.11.2010, 01:37

Код


subset([], []).

subset([X | SubSet], [X | Set]) :-
    subset(SubSet, Set).

subset(SubSet, [_ | Set]) :-
    subset(SubSet, Set).

И, правда, работает.
PS пролог изучаю пару недель, поэтому сразу не допёр.

Автор: Cheloveck 23.11.2010, 01:52

Тут, кстати, получаются только упорядоченные подмножества

Код


?- subset(L, [1,2,3,4]).
L = [1, 2, 3, 4] ;
L = [1, 2, 3] ;
L = [1, 2, 4] ;
L = [1, 2] ;
L = [1, 3, 4] ;
L = [1, 3] ;
L = [1, 4] ;
L = [1] ;
L = [2, 3, 4] ;
L = [2, 3] ;
L = [2, 4] ;
L = [2] ;
L = [3, 4] ;
L = [3] ;
L = [4] ;
L = [] ;
false.

Код


?- subset([2,1], [1,2,3,4]).
false.

Автор: Coderr 23.11.2010, 03:17

Эх, я был близок. Первую и третью строки я писал, но не понял как разделить дальше на условия. =)

Спасибо тебе, добрый Cheloveck, листинг работает как надо. smile

А как работают строки

Код


subset([X | SubSet], [X | Set]) :-
    subset(SubSet, Set).
subset(SubSet, [_ | Set]) :-
    subset(SubSet, Set).

Автор: Cheloveck 23.11.2010, 10:24

Цитата(Coderr @ 23.11.2010, 03:17

)

А как работают строки

Именно так и работают =)

Цитата(Coderr @ 22.11.2010, 22:46

)

Чтобы определить, является ли Подмножество подмножеством Множества, надо последовательно проходить по ним и, если первые их элементы совпадают, отсекать эти первые элементы и продолжать сравнивать оставшиеся списки. Если первые элементы не совпадают, надо отсекать у Множества первый элемент и сравнивать оставшийся список с Подмножеством.

Добавлено через 4 минуты и 47 секунд
кстати, есть изумительный предикат

Код


trace.

после выполнения которого все достежение всех других целей будет показано подробно. Для выхода из трассировки надо сделать

Код


notrace, nodebug.

Автор: Coderr 23.11.2010, 16:04

Спасибо!