prolog - 寻找最大最小值集

Question

我正在尝试编写一个(天真的或半天真的)程序，给定一组元素和一些玩家将其划分为这个数量的玩家，并且对于每个这样的划分取最小值(通过总和)子集。然后，我想计算所有这些最小除法的最大值。

这被称为 https://en.wikipedia.org/wiki/Maximin_share .

例如，如果我们查看集合 {1,4,6}，我们可以将其分配给 2 个玩家，这样一个玩家收到 {1,4}，另一个玩家收到 {6}，这里的最小值是 5。对于所有其他划分，很容易看出最小值将小于 5。

我想写一个 prolog 谓词 maximin(+Elements,+Players,-Value) 给定 Elements(正整数)列表和一些 Players 返回最大值 Value。

我尝试了一种非常幼稚的方法:

1. 写了一个计算特定除法的谓词。
2. 使用 find all 找到所有部门。
3. 对于每个分区返回最小子集的值。
4. 计算出它们中的最大值。

但是，该程序仅针对少量输入运行。例如，如果我采用一个包含 10 个元素的列表 Elements 并尝试将其划分为 3 个玩家，我会收到堆栈外的错误，即使我试图增加使用 set_prolog_stack 尽我所能地存储程序。

我的代码:

% returns the smaller item
mini(A,B,B):- A > B.
mini(A,B,A):- A =< B.

% Returns the Sum of the minimal subset in a division (+,-)
min_subset_value([P1],Sum1):-subset_value(P1,Sum1).
min_subset_value([P1|RestP],Min) :-  RestP \= [], min_subset_value(RestP, OtherMin), subset_value(P1,A1)
                                     , mini(A1, OtherMin, Min).


% divide_to_players(+,+,-) : Generate a division of all the Elements to N subsets
divide_to_players([],N,EmptySets):- N>=1, generate_empty_sets(EmptySets,N).
divide_to_players(Elements, 1, [Elements]):-Elements \= [].
divide_to_players(Elements, N, [P1|RestP]):- N>1, Elements \= [], subseti(P1,Elements)
                                             , remove_subset(Elements,P1,OtherElements)
                                             , N1 is N-1
                                             , divide_to_players(OtherElements, N1, RestP).
% Generates all divisions (+,+,-)
generate_all_divisions(Elements,N,AllDivs) :- findall(Div,divide_to_players(Elements,N,Div),AllDivs).

% From all the given divisions, which one has the maximal minimal subset
find_max_division([],0).
find_max_division([Set1|RestSets],Max) :- find_max_division(RestSets, OtherMin)
                                         , min_subset_value(Set1,LocalMin)
                                         , maxi(LocalMin, OtherMin, Max).

% uses the previous functions as described above (+,+,-)
maximin_player(Elements,N,Maximin) :- generate_all_divisions(Elements,N,AllDiv)
                                     , find_max_division(AllDiv,Maximin).

但是，我正在徘徊是否有另一种方法可以继续呢？也许不使用 findall 就可以找到最大值？我只使用 findall 因为我没有更好的方法，所以我很高兴听到其他想法或方法来解决这个问题。

Answer 1

如果元素都是整数(即没有变量也没有浮点值)我相信这工作正常:

maximin(Elements, N, Maximin, LDistribution):-
  sumlist(Elements, Sum),
  TargetMaximin is -Sum//N,
  once(
  (
    between(TargetMaximin, -1, NMaximin),
    Maximin is -NMaximin,
    distribute(Elements, [], n, Maximin, N, 0, [], LDistributionOnce)
  )),
  LDistribution=LDistributionOnce.
  
distribute([], [], _, _, 0, _, _, []).
distribute(Elements, Skipped, y, Maximin, N, Cur, Distribution, [Distribution|LDistribution]):-
  N>0,
  Cur >= Maximin,
  succ(N1, N),
  append(Elements, Skipped, NElements),
  distribute(NElements, [], n, Maximin, N1, 0, [], LDistribution).
distribute([Element|Elements], Skipped, _, Maximin, N, Cur, Distribution, LDistribution):-
  N>0,
  NCur is Cur+Element,
  distribute(Elements, Skipped, y, Maximin, N, NCur, [Element|Distribution], LDistribution).
distribute([Element|Elements], Skipped, _, Maximin, N, Cur, Distribution, LDistribution):-
  N>0,
  distribute(Elements, [Element|Skipped], n, Maximin, N, Cur, Distribution, LDistribution).

该算法的思想是从最大目标mininum值(元素总和除以玩家人数的整数除法)开始，尝试将元素拟合到N个槽位中，其中每个槽位总和至少为目标最低。如果您找到这样的分布，那么您就完成了，否则将目标最小值减 1 并重复。

这里的算法也给出了它找到的唯一一个分布。

样本运行:

?- maximin([11,17,19],3,Maximin, LDist).
Maximin = 11,
LDist = [[11], [17], [19]].

?- maximin([5,7,1,3,3,7,4,3,8,2,5,1],3,Maximin, LDist).
Maximin = 16,
LDist = [[3, 1, 7, 5], [3, 4, 7, 3], [1, 5, 2, 8]].