Prolog中互斥事件定义及指定总容量存储组合求解技术咨询

嘿，这个问题用Prolog来解决简直量身定做！核心要处理两个关键约束：每个盒子只能用一次的互斥规则，以及选中的4个盒子总尺寸恰好230平方厘米。下面是具体的实现思路和代码：

• 从5个给定盒子里挑选4个，必须保证每个盒子仅被使用一次（互斥，不能重复分配）
• 选中的4个盒子尺寸总和必须严格等于230
• 区分两种场景：如果不看重存储空间的顺序（比如把50放在第一个还是第二个空间不算不同分配），那我们找的是组合；如果区分顺序，那就是找排列

% 定义所有可用的盒子尺寸
boxes([50, 50, 50, 80, 90]).

% 主谓词：获取所有有效的分配场景
find_valid_allocations(Allocations) :-
    boxes(Boxes),
    % 收集所有满足条件的4元组合
    findall(Selected, 
            (select_4_unique(Boxes, Selected), sum_list(Selected, 230)), 
            Allocations).

% 辅助谓词：从列表中选4个不重复的元素（处理重复值的情况）
select_4_unique(List, Selected) :-
    subset(List, Selected),
    length(Selected, 4),
    % 确保选中的元素在原列表中有足够的出现次数（比如原列表只有3个50，不能选超过3个）
    count_occurrences(Selected, SelectedCounts),
    count_occurrences(List, ListCounts),
    forall(member((Item, Count), SelectedCounts), 
           (member((Item, ListCount), ListCounts), Count =< ListCount)).

% 辅助谓词：统计列表中每个元素的出现次数
count_occurrences(List, Counts) :-
    sort(List, Sorted),
    count_occurrences_loop(Sorted, [], Counts).

count_occurrences_loop([], Acc, Acc).
count_occurrences_loop([X|Rest], Acc, FinalCounts) :-
    count_consecutive(X, Rest, 1, NewRest),
    count_occurrences_loop(NewRest, [(X, 1)|Acc], FinalCounts).

count_consecutive(X, [X|Rest], Current, NewRest) :-
    NewCurrent is Current + 1,
    count_consecutive(X, Rest, NewCurrent, NewRest).
count_consecutive(_, Rest, _, Rest).

代码解释 #

• boxes/1：直接定义我们拥有的所有盒子尺寸，方便后续调用。
• find_valid_allocations/1：作为入口，用findall/3收集所有符合条件的解——它会遍历所有可能的4元组合，筛选出总和为230的那些。
• select_4_unique/2：处理选4个不重复元素的需求，这里的“不重复”是指不能超过原列表中元素的实际出现次数（比如原列表有3个50，最多选3个），而非元素值唯一。
• count_occurrences/2系列谓词：用来统计每个元素的出现次数，避免出现“选了4个50”这种不符合实际的情况。

如果每个存储空间的位置是有区别的（比如把80放在第一个空间和第二个空间算不同分配场景），只需要把select_4_unique/2替换成下面的版本：

select_4_unique(List, Selected) :-
    permutation(List, Permuted),
    length(Selected, 4),
    append(Selected, _, Permuted).

这个版本会生成所有可能的4元素排列，每个排列对应一种不同的存储空间分配顺序。

在Prolog解释器中运行：

?- find_valid_allocations(Allocations).

• 组合版本会返回：Allocations = [[50,50,50,80]]（只有这一种组合满足总和230）
• 排列版本会返回4种不同的分配场景：[[50,50,50,80], [50,50,80,50], [50,80,50,50], [80,50,50,50]]

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