3

这个问题与Seeking a solution or a heursitic approxmation for the 3-partitioncombinatorial situation中描述的上下文有关。任务是将大约 48 件继承的珠宝,每件都有其评估价值,分配给 3 位继承人,以使每位继承人的价值相等或几乎相等。就我的法律目的而言,这个问题已经得到了充分的回答。

这个新问题源于我通过枚举解决这个问题的追求。在法律上完全没有必要。现在只是一个智力挑战。

现在的问题:

为每个项目分配一个唯一索引:可能只是整数 1 到 48。现在将这 48 个分配给 3 个继承者中的每一个并消除重复项。

为了使这个例子更简单,断言只有 9 个项目,每个继承者将接收 3 个项目。(请注意,这与之前使 3 个 bin 的值几乎相等的目标不同。)

如何消除 item-to-bins 序列中的重复项?

示例:
让 bin 1 包含项目 {1,2,3}
让 bin 2 包含项目 {4,5,6}
让 bin 3 包含项目 {7,8,9}

这个三元组的最终值将有 6 个重复:
{1,2,3}{4,5,6}{7,8,9}
{4,5,6}{1,2, 3}{7,8,9}
{4,5,6}{7,8,9}{1,2,3}
{7,8,9}{1,2,3}{4,5,6 }
{7,8,9}{4,5,6}{1,2,3}
等。

同样,如何消除 item-to-bins 序列中的重复项?不枚举整个三元组排列。不,这不太对。我可能不得不暂时磨掉所有的三元组排列。如何根据已经完成的先验快速消除重复的三元组组合?

我可以想象像发明一个函数,给定 3 个项目的任意组合,返回一个唯一值。使用素数的东西?除了许多素数对和另一个素数。

我交叉发布了关于 mathoverflow 的原始问题。对于不理解 stackoverflow 和 mathoverflow 之间的关系,我深表歉意。

4

2 回答 2

3

可以证明受限分区的总数为

在此处输入图像描述,等于 280。

这可以重新排序为:

在此处输入图像描述

您可以通过从九个列表成员中取出三个获得的(有序)组合的前三分之一以及前三个中的每个选择从剩余六个中取出三个时获得的组合的前半部分来得到这个. 最后三个当然没有自由选择。

使用 Mathematica,您可以将其生成为:

list = Range[9];
l1 = Subsets[list, {3}, Binomial[9, 3]/3];
l2 = Subsets[Complement[list, #], {3}, Binomial[6, 3]/2] & /@ l1;
Flatten[
  Outer[
    Function[{ll1, ll2}, {ll1, ll2, Complement[list, ll1, ll2]}], 
    {#1}, #2, 1, 1
  ] & @@@ ({l1, l2}\[Transpose]), 
2]

在此处输入图像描述

于 2011-12-28T23:09:02.687 回答
2

这是一个很好的问题。它本质上是一个受限集分区问题。

这是您可以解决此问题的一种方法。我不确定它是否是最优的,但它比蛮力(生成所有排列然后删除重复项)更有效。

我将使用大括号来表示列表,因为这对我来说很熟悉。

从这个模板开始,它代表三个箱子中的零个项目:

{ {{}, {}, {}} }

对于最外面的每个列表(即{{}, {}, {}}此处):

  1. 追加1到每个子列表,跳过所有已满的列表(包含三个元素),{}如果有多个列表,则仅追加到第一个空列表。

  2. 为每个替换项保留整个列表的副本,并在步骤结束时将它们连接在一起。

然后将针对23等重复此过程,直到所有项目都在箱中或所有箱都已满。示例步骤:

{ {{}, {}, {}} }

{ {{1}, {}, {}} }

{ {{1, 2}, {}, {}}, {{1}, {2}, {}} }

{ {{1, 2, 3}, {}, {}}, {{1, 2}, {3}, {}}, {{1, 3}, {2}, {}}, {{1}, {2, 3}, {}}, {{1}, {2}, {3}} }

{ {{1, 2, 3}, {4}, {}}, {{1, 2, 4}, {3}, {}}, {{1, 2}, {3, 4}, {}}, {{1, 2}, {3}, {4}}, {{1, 3, 4}, {2}, {}}, {{1, 3}, {2, 4}, {}}, {{1, 3}, {2}, {4}}, {{1, 4}, {2, 3}, {}}, {{1}, {2, 3, 4}, {}}, {{1}, {2, 3}, {4}}, {{1, 4}, {2}, {3}}, {{1}, {2, 4}, {3}}, {{1}, {2}, {3, 4}} }
于 2011-12-22T08:22:30.347 回答