CODEWITHSUNDEEP
prologconstraint-programming
Antobiotics
Antobiotics

Reputation: 75

Prolog, how to order a list with constraints

I am quite new with Prolog and I am trying to use it to order a list with defined constraints.

The problem starts with the following definitions:

For example:

With the items:

item_1 = [chicken, meat, 1.0]
item_2 = [eggplant, vegetable, 0.5]
item_3 = [tomatoes, vegetable, 1.0]
item_4 = [bread, other, 0.2]

We build two Contents: 

contentA = [item_2, item_3]
contentB = [item_1, item_4]
contentC = [item_3, item_4]

So now, let's say we have some content defintions:

hasItemType([_, XType, _], XType).

hasListItemType([H|T], Type) :-
    hasItemType(H, Type);
    hasListItemType(T, Type).

hasListOnlyItemType([H|T], Type) :-
    hasItemType(H, Type),
    hasListItemType(T, Type)

isVegetarian(Content) :- hasListOnlyItemType(Content, vegetable).
hasVegetables(Content) :- hasListItemType(Content, vegetable).
hasMeat(Content) :- hasListItemType(Content, meat).

The goal would be:

Given a list of Content returns a ContentList that matches the best a defined order:

For example (but thus my question i'm not sure if it is the right way of doing it.) 

 -> `order(A, B)` A is before B in the output list.


order(ContentA, ContentB) :-
    isVegetarian(ContentA),
    hasVegetables(ContentB).

order(ContentA, ContentB) :-
    hasVegetables(ContentA),
    hasMeat(ContentB).

Ideally, I would like something like that:

solve([contentB, contentC, contentA]) to would return [contentA, contentB, contentC]

because: order(contentA, contentB), order(contentA, contentC), order(contentB, contentC)

So I have basically two questions:

  1. Is it a reasonable way to formalise my problem.
  2. Once the order and constraints are correctly defined, what would be the way to write a solver?

I understand my question is a bit wide, so I will take any suggestions, references, ideas ;)

Thanks in advance if you read this!

Upvotes: 1

Views: 508

Answers (1)

coder
coder

Reputation: 12972

What you need is a sorting function but not sorting with standard comparing functions-predicates like =< or >= but with using your order predicate. So you need to implement a sorting algorithm in Prolog, for example insertion sort:

insertionSort([], []).

insertionSort([HEAD|TAIL], RESULT) :-
   insertionSort(TAIL, LIST), insertInPlace(HEAD, LIST, RESULT).

insertInPlace(ELEMENT, [], [ELEMENT]).

insertInPlace(ELEMENT, [HEAD|TAIL], [ELEMENT|LIST]) :-
   order(ELEMENT,HEAD), insertInPlace(HEAD, TAIL, LIST).

insertInPlace(ELEMENT, [HEAD|TAIL], [HEAD|LIST]) :-
   \+order(ELEMENT ,HEAD), insertInPlace(ELEMENT, TAIL, LIST).

You could also implement mergesort which is more efficient. Since I have no data I can't see if the above is really working or if it has some bugs so I'm waiting for comments...

I think it works I tested it by querying:

insertionSort([[[chicken, meat, 1.0],[beaf, meat, 1.0]],[[eggplant, vegetable, 0.5],[tomatoes, vegetable, 1.0]]],Result).

where I gave a list [content1,cntent2] where content1 had type meat and content 2 had type vegetable so according to order predicate the output should be [content2,content1] so the output I think is right:

?- insertionSort([[[chicken, meat, 1.0],[beaf, meat, 1.0]],[[eggplant, vegetable, 0.5],[tomatoes, vegetable, 1.0]]],Result).
Result = [[[eggplant, vegetable, 0.5], [tomatoes, vegetable, 1.0]], [[chicken, meat, 1.0], [beaf, meat, 1.0]]] ;
false.

Upvotes: 1

Related Questions