如何枚举并删除以三元组形式分配给 3 个继承人中的每一个的 9 个项目......以及更多？
该问题与寻求 3 分区组合情况的解决方案或启发式近似中描述的上下文相关。任务是将大约48件继承的珠宝，每件都有其评估价值，分配给3名继承人，使每个继承人的价值相等或接近相等。对于我的法律目的来说，这个问题已经得到了充分的回答。
这个新问题源于我试图通过枚举来解决这个问题。法律上完全没有必要。现在只是智力挑战。
现在的问题是：
为每个项目分配一个唯一索引：可能只是整数 1 到 48。现在将这 48 个分配给 3 个继承者中的每一个，并消除重复项。
为了使这个示例更简单，断言只有 9 个项目，并且每个继承者将恰好接收 3 个项目。 （请注意，这与之前使 3 个垃圾箱价值几乎相等的目标不同。）
如何消除项目到垃圾箱序列中的重复项？
示例：
让箱 1 包含项目 {1,2,3}
让箱 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}
等等。
同样，如何消除物品到垃圾箱顺序中的重复？无需枚举整个三元组排列。不，这不太正确。我可能不得不暂时磨出所有三元组的排列。如何根据先验结果快速消除重复的三元组组合？
我可以想象类似发明一个函数，给定 3 个项目的任意组合，返回一个唯一的值。使用素数的东西？只不过许多对素数之和是另一个素数。
我在 mathoverflow 上交叉发布了原始问题。我很抱歉不理解 stackoverflow 和 mathoverflow 之间的关系。
This question is related to the context described in Seeking a solution or a heursitic approxmation for the 3-partition combinatorial situation. The task is distribute approximately 48 pieces of inherited jewelry, each with its appraised value, to 3 inheritors so as to give each inheritor equal or nearly equal value. That question has been sufficiently answered for my legalistic purposes.
This new question arises out of my pursuit of solving this by enumeration. Totally unnecessary legally. Just an intellectual challenge now.
The problem now:
Assign to each item a unique index: probably just the integers 1 through 48. Now allocate these 48 to each of the 3 inheritors and eliminate the duplicates.
To make this example case simpler, assert that there are only 9 items and each inheritor is to receive exactly 3 items. (Note that this diverges from the previous goal of making the 3 bins of nearly equal value.)
How to eliminate the duplications in the sequence of items-to-bins?
Example:
Let bin 1 contain items {1,2,3}
Let bin 2 contain items {4,5,6}
Let bin 3 contain items {7,8,9}
There will be 6 duplications of the final values of this triplet-of-triplets:
{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}
etc.
Again, how to eliminate the duplications in the sequence of items-to-bins? Without enumerating the entire set of permutations-of-triplets. No, that's not quite right. I might have to temporarily grind out all the permutations-of-triplets. How to quickly eliminate the duplicated combinations-of-triplets based on what has been done a priori?
I can imagine something like inventing a function which, given any combination of 3 items, returns a unique value. Something using prime numbers? Except that many pairs of prime numbers sum to another prime number.
I crossposted the original question on mathoverflow. I apologize for not understanding the relationship between stackoverflow and mathoverflow.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
可以看出，受限分区的总数为
这可以重新排序为：
您可以通过获取（有序）组合的前三分之一来获得此组合，方法是从以下组合中取出三个九名单成员以及前三个选项中的每个选项从剩余六个中取出三个时获得的组合的前半部分。当然，最后三个没有自由选择。
使用 Mathematica，您可以将其生成为：
One can show that the total number of restricted partitions is
This can be reordered as:
You can get this by taking the first third of the (ordered) combinations you obtain by taking three out of nine list members and the first half of the combinations you get when you take three out of the remaining six for each choice of the first three. There's no free choice for the last three of course.
With Mathematica you might generate this as:
这是一个好问题。它本质上是一个受限集划分问题。
这是您可以解决此问题的一种方法。我不确定它是否是最优的，但它比蛮力（生成所有排列然后删除重复项）更有效。
我将使用大括号来表示列表，因为这对我来说很熟悉。
从这个模板开始，它代表三个容器中的零个项目：
对于最外面的每个列表（即这里只是
{{}, {}, {}}）：Append
1到每个子列表，跳过任何已满的列表（包含三个元素），并且仅附加到第一个空{}列表（如果有多个子列表）。为所做的每个替换保留整个列表的副本，并在步骤结束时将它们连接在一起。
然后将对
2、3等重复此过程，直到所有物品都放入垃圾箱或所有垃圾箱已满。步骤示例：This is a good question. It is essentially a restricted set partition problem.
Here is one way in which you may approach this. I am not certain that it is optimal, but it is many magnitudes more efficient than brute force (generating all permutations and then removing duplicates).
I will be using curly brackets to represent lists, as this is familiar to me.
Start with this template, which represents zero items in three bins:
For each list within the outermost (i.e. just
{{}, {}, {}}here):Append
1to each sub-list, skipping any lists that are full (contain three elements), and append only to the first empty{}list if there is more than one.Keep a copy of the entire list for each replacement that is made, and join these together at the end of the step.
This process will then be repeated for
2,3, etc., until all items are in bins or all bins are full. Example steps: