prolog

Prolog - get best value among permutations of list


In Prolog, i have a simple list of twelve strings. I also have a list of rules that together assign a score to that list. So according to how those elements are placed in my list, they may or may not break a rule.

I need to find the permutation of that list that gives me the highest possible score. How can i do that?

Here is what i have:

compute(InitialSettings, NewSettings, NewSettingsScore):-
    perm(InitialSettings, NewSettings),
    check_bonds(NewSettings, NewSettings, -1, 0, NewSettingsScore).

I omitted the code inside check_bonds because it's not relevant to the question and it would only make it more complicated. Basically i need to loop through all the permutations and find the one that has the highest NewSettingsScore. Is there any way to do this? Thanks in advance!


Solution

  • A very simple solution sould be generating all the permutations and then select the one with the highest associated score. In SWI you can write

    assign_score(_L,1).
    solve(L,Best):-
        findall(LO,permutation(L,LO),LP),
        maplist(assign_score,LP,Ls),
        max_list(Ls,Best).
    

    For simplicity, I assume that all the lists have the same score, since I don't know how they are computed. You get:

    ?- solve([1,2,3],B).
    B = 1.
    

    It can be easily extended to also get the list with the highest score. Moreover, depending on the score computation, you can prune some of the lists while evluating them, so speeding up the process.