Prolog程序推理次数优化求助：减少甜点生成逻辑的推理量

问题背景 #

我正在尝试减少Prolog程序的推理次数，需求对应两个场景：一是实现列表的列表间的比较约束，二是将列表拆分为指定大小的子列表构成的列表。

当前代码 #

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).

性能问题 #

执行以下查询时，推理次数超过400万：

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]].

单独测试各谓词时推理量不高，推测核心问题是全排列生成后再过滤的流程效率极低，需从提前剪枝、约束前置方向优化。

优化建议 #

1. 替换“全排列+拆分”为直接生成分组 #

当前流程先生成全排列（9! = 362880种可能），再拆分成分组，大部分排列会被后续约束过滤，完全浪费资源。应直接生成满足大小要求的不相交分组，覆盖所有元素，避免无效排列生成。

2. 约束前置，边生成边检查 #

每生成一个分组，立刻检查其与Starter、Main中所有分组的公共元素约束，不满足则直接回溯，无需生成完整的Dessert列表，大幅剪枝无效分支。

3. 优化公共元素检查逻辑 #

原代码用intersection生成所有公共元素再统计长度，效率低下。改为遍历元素时实时计数，一旦公共元素超过1就立刻终止检查，减少不必要的遍历。

优化后代码示例 #

make_dessert(Starter, Main, Dessert, List_of_Persons, Size):-
    length(List_of_Persons, Total),
    NumGroups is Total // Size,
    generate_valid_groups(List_of_Persons, Size, NumGroups, Starter, Main, Dessert).

% 生成指定数量的合法分组，覆盖所有元素
generate_valid_groups([], _, 0, _, _, []).
generate_valid_groups(Remaining, Size, NumGroups, Starter, Main, [Group|Rest]):-
    NumGroups > 0,
    select_n(Size, Remaining, Group, NewRemaining),
    group_valid(Group, Starter),
    group_valid(Group, Main),
    NextNumGroups is NumGroups - 1,
    generate_valid_groups(NewRemaining, Size, NextNumGroups, Starter, Main, Rest).

% 从列表中选择N个元素作为分组，返回剩余元素
select_n(0, List, [], List).
select_n(N, List, [X|Xs], Rest):-
    N > 0,
    select(X, List, Temp),
    N1 is N - 1,
    select_n(N1, Temp, Xs, Rest).

% 检查分组与目标列表中所有组的公共元素数量不超过1
group_valid(_, []).
group_valid(Group, [G|Gs]):-
    count_common(Group, G, 0, L),
    L =< 1,
    group_valid(Group, Gs).

% 实时统计公共元素数量，超过1则直接失败
count_common([], _, Acc, Acc).
count_common([X|Xs], G, Acc, L):-
    (member(X, G) -> NewAcc is Acc + 1; NewAcc = Acc),
    NewAcc =< 1,
    count_common(Xs, G, NewAcc, L).

优化效果说明 #

• 生成分组的组合数仅为C(9,3)*C(6,3)*C(3,3) = 1680，远小于原流程的362880次排列
• 每生成一个分组就做约束检查，无效分支提前被剪枝
• 公共元素统计提前终止，减少推理步骤

内容的提问来源于stack exchange，提问作者snow_white