Graphs in Prolog

Question

I'm new to Prolog and I need some help :D

I learned recursion and I know how to use it (more or less). I'm having troubles with graphs. I'm trying to solve Knapsack problem, so I'm making one step at time.

MY PROBLEM: I have a list of types and I'd like to make all the sublist with length n(=3) and pick the one with biggest value. I think I need a function that pulls out the head of the list of types and passes it to another function that calulates recursively the "sons". My idea was something like this:

append([],L2,L2):- !.
append([T|C],L2,[T|L3]):-
    append(C,L2,L3).

genera_ext(_,[],_).

genera_ext(Padre,[TT|CT],Figlio):-
    genera(Padre,TT,[TT|CT],Figlio),
    genera_ext(Padre,CT,[]).

genera(Padre,Elem,L_tipi,Figlio):-
    append(Padre,[Elem],Base),
    copy_term(Figlio,Base),
    length(Base,Lun),
    Lun =< 3,
    genera_ext(Base,L_tipi,Temp),
    total_ing(Temp,I_Temp),
    total_ing(Base,I_Base),
    I_Temp >= I_Base,
    copy_term(Figlio,Temp),
    nl,write("Figlio = "),write(Figlio).

genera(_,_,_,_).

There's obviously something wrong. Could you help me? Thanks :( M.R.

edit:

I have some facts

art(xxx,weight_xxx).

and this is the function that calculates the weight of a list made of elements xxx

total_ing([],0).
total_ing([X|C],I0):-
    art(X,N),
    total_ing(C,I1),
    I0 is I1 + N.

I call it

genera_ext([],L_tipi, Figlio)

where L_tipi is the list of elements xxx I can choose.

I'd like to generate all the possible sublists of elements xxx with length 3 and pick the one with the biggest weight.

Answer 1

I'd like to generate all the possible sublists of elements xxx with length 3 and pick the one with the biggest weight.

This is a classic "generate-and-test" question. And you could solve it in kind of a naive way, by generating all possible permutations of the art, with something like this:

inefficient([A1,A2,A3], Sum) :-
    art(A1, X),
    art(A2, Y),  A2 \= A1,
    art(A3, Z),  A3 \= A2, A3 \= A1,
    Sum is X+Y+Z.

inefficient_best(L, Sum) :-
    inefficient(L, Sum),
    \+ (inefficient(L2, Sum2), L2 \= L, Sum2 > Sum).

Calling this inefficient is extremely kind; it really is trying every permutation against every other permutation multiple times, and it will generate multiple solutions that are just the same sequence permuted. But it does "work."

The next thing to think about is how to make it more efficient. There isn't an obvious thing to do to make the test faster, but the generate step is definitely creating a bunch of wasteful combinations. The first thing we could do is materialize the database into a list using findall/3 and then use permutation/2 to generate permutations to try. But this feels to me like it would be about as bad. I started to think the best way forward was making a predicate for generating combinations of a certain length. I couldn't think of a better way to do this using the built-in predicates (maybe there is one and I'm just not being clever enough) but I came up with this:

combination(0, _, []) :- !.
combination(N, [X|Xs], [X|Ys]) :-
    succ(N0, N),
    combination(N0, Xs, Ys).
combination(N, [_|Xs], Ys) :-
    combination(N, Xs, Ys).

This produces results like so:

?- combination(3, [a,b,c,d,e], X).
X = [a, b, c] ;
X = [a, b, d] ;
X = [a, b, e] ;
X = [a, c, d] ;
X = [a, c, e] ;
X = [a, d, e] ;
X = [b, c, d] ;
X = [b, c, e] ;
X = [b, d, e] ;
X = [c, d, e] ;
false.

The way this works is basically to either take the current item in the list and reduce the length we still need by one, or recur without taking the current item. It's a lot like member/2.

So now that we have this we can materialize the database and do less work trying all the permutations. In fact we can use sort/2 to find the winner, assuming you want just one result, but we'll need a helper function first:

art_cost(ArtList, Cost-ArtList) :-
    maplist(art, ArtList, CostList),
    sumlist(CostList, Cost).

art_cost/2 calculates the total cost of a list of art, but returns a pair: the cost with the actual artlist. This kind of thing is not terribly uncommon, and we rely on it in the next step for our predicate to find the highest costs:

best(ArtList, Cost) :-
    % materialize the list of all artworks
    findall(A, art(A,_), Art),

    % materialize the list of candidate combinations
    findall(Candidate, combination(3, Art, Candidate), Candidates),

    % compute the cost+list for all the candidate lists
    maplist(art_cost, Candidates, CostsWithArtLists),

    % sort the list, which will put them in order of cost
    % but lowest-to-highest
    sort(CostsWithArtLists, CostsLowToHigh),

    % flip the list around and deconstruct the highest 
    % as our result
    reverse(CostsLowToHigh, [Cost-ArtList|_]). 

There is probably a more efficient way to do this with library(aggregate), but I wasn't able to figure it out.

As an aside, I don't think you need copy_term/2 in your code at all, and I'm always suspicious when I see terms that look like a bunch of anonymous variables: genera(_,_,_,_)—it seems unlikely to me that you mean "genera holds for any four things."