I am trying to lower the inferences needed for executing my program in Prolog. My task is exactly the same as in: Prolog: Comparing Lists from Lists of Lists and Prolog - split a list into lists of lists. My code so far:
make_dessert(Starter, Main, Dessert, List_of_Persons, Size):-
permutation(List_of_Persons, Permuted),
split_list(Permuted, Size, Dessert),
at_most_one_common(Starter, Dessert),
at_most_one_common(Main, Dessert).
split_list(List, N, Splitted_List) :-
split_helper(List, N, [], Splitted_List).
split_helper([], _, Acc, Acc).
split_helper(List, N, Acc, Splitted_List) :-
append(H, T, List),
length(H, N),
split_helper(T, N, [H|Acc], Splitted_List).
at_most_one_common([], _).
at_most_one_common([H|T], List2) :-
check_list(H, List2),
at_most_one_common(T, List2).
check_list(_, []).
check_list(X, [H|T]) :-
intersection(X, H, Z),
length(Z, L),
L =< 1,
check_list(X, T).
Following query generates more than 4,000,000 inferences:
make_dessert([[1,2,3],[4,5,6],[7,8,9]],[[1,4,7],[2,5,8],[3,6,9]], D, [1,2,3,4,5,6,7,8,9], 3)).
% 4,380,057 inferences, 0.281 CPU in 0.286 seconds (98% CPU, 15578798 Lips)
D = [[3, 4, 8], [2, 6, 7], [1, 5, 9]].]
As all predicates tested by themselves alone are not producing a high number of inferences at all. I am seeing space for improvement in maybe finding the right permutation faster? Or maybe if one permutation is proofed to not fulfil the constraints to stop processing earlier on? I am grateful for any small improvement.
permutation creates too many unwanted, erm, permutations. Instead, choose "1 from each segment", to greatly reduce the search space:
permute_segments(Segs, Perm) :-
% Perm will have the same list-of-lists structure
same_length(Segs, Perm),
permute_segments_(Perm, Segs).
permute_segments_([], _).
permute_segments_([E|T], Segs) :-
% Populate each segment of Perm
select_segments(Segs, E, Segs0),
permute_segments_(T, Segs0).
select_segments([], [], []).
select_segments([H|T], [E|P], [H0|L]) :-
% Populate each element of Perm
select(E, H, H0),
select_segments(T, P, L).
Result in swi-prolog:
?- permute_segments([[1,2,3],[4,5,6],[7,8,9]], P).
P = [[1, 4, 7], [2, 5, 8], [3, 6, 9]] ;
P = [[1, 4, 7], [2, 5, 9], [3, 6, 8]] ;
...
P = [[3, 6, 9], [2, 5, 7], [1, 4, 8]] ;
P = [[3, 6, 9], [2, 5, 8], [1, 4, 7]].
To show the efficiency improvement:
?- bagof(P, permute_segments([[1,2,3],[4,5,6],[7,8,9]], P), Ps), length(Ps, Len).
Len = 216.
?- bagof(P, permutation([1,2,3,4,5,6,7,8,9], P), Ps), length(Ps, Len).
Len = 362880.