具有约束条件的随机分配物品算法

Question

帮我找一个好的算法吗？

我有一个装有n个球的袋子。 （以28个球为例）

这个袋子里的每个球都有一种颜色。袋子里最多有4种不同颜色的球。（例如，红色，绿色，蓝色和紫色是可能的颜色。）

我有三个桶，每个桶都有一个数字，表示它们需要最终拥有的球的数量。这些数字总共为n。（例如，假设桶A需要最终拥有7个球，桶B需要最终拥有11个球，桶C需要最终拥有10个球。）

这些桶也可能有颜色限制 - 它们不接受的颜色。（桶A不接受紫色球或绿色球。桶B不接受红色球。桶C不接受紫色球或蓝色球。）

我需要有效且随机地分配这些球（所有可能性的概率相等）。

我不能只是将球随机放在有空间可以接受它们的桶中，因为那可能会导致出现这样一种情况：唯一有剩余空间的桶不接受袋子中仅剩的颜色。

已知总是有至少一种分配球的可能性。（我不会拥有只有红色球的袋子，而某个数量> 0的桶不接受红色球。）

即使它们是相同的颜色，所有球都被认为是不同的。（桶C获得红球1而不是红球2的可能性之一与除了桶C获得红球2而不是红球1之外其他所有内容相同的可能性是不同的。）

编辑以添加我的想法：

我不知道这是否具有所有可能性的等概率性，因为我希望如此。我还没有找出效率 - 它似乎不太糟糕。并且这包含一个我不确定是否始终正确的断言。如果您知道任何这些事情，请在评论中提出意见。

Choose a ball from the bag at random. (Call it "this ball".)

If this ball fits and is allowed in a number of buckets > 0:
    Choose one of those buckets at random and put this ball in that bucket.

else (this ball is not allowed in any bucket that it fits in):
    Make a list of colors that can go in buckets that are not full.
    Make a list of balls of those colors that are in full buckets that this ball is allowed in.
    If that 2nd list is length 0 (There are no balls of colors from the 1st list in the bucket that allows the color of this ball):
        ASSERT: (Please show me an example situation where this might not be the case.)
                There is a 3rd bucket that is not involved in the previously used buckets in this algorithm.
                (One bucket is full and is the only one that allows this ball.
                 A second bucket is the only one not full and doesn't allow this ball or any ball in the first bucket.
                 The 3rd bucket is full must allow some color that is in the first bucket and must have some ball that is allowed in the second bucket.)
        Choose, at random, a ball from the 3rd bucket balls of colors that fit in the 2nd bucket, and move that ball to the 2nd bucket.
        Choose, at random, a ball from the 1st bucket balls of colors that fit in the 3rd bucket, and move that ball to the 3rd bucket.
        Put "this ball" (finally) in the 1st bucket.
    else:
        Choose a ball randomly from that list, and move it to a random bucket that is not full.
        Put "this ball" in a bucket that allows it.
Next ball.

- beauxq

---

“有效且随机地分发球” 是什么意思？您是在寻找所有可能性，还是只需要一种呢？ - m69 ''snarky and unwelcoming''

@m69 算法执行一次将产生一种可能性。但它是随机的。这意味着，下一次使用相同输入运行算法时，它可能会得出不同的可能性。理想情况下，所有可能性应具有相等的概率。 - beauxq

球是从袋子里随机取出来的，还是在从袋子里取出后随机分配到桶中的？如果第一次运行程序时球按顺序[1, 7, 3, 4, 2, 6, 5]从袋子中取出，第二次再次运行程序，您是否期望算法会产生不同的输出结果？ - Jim Mischel

一个正确的随机解决方案需要满足所有约束条件的结果集中，每个结果出现的概率相等。关于什么是随机的猜测很容易出错。除非你通过列举所有合法结果并选择一个具有均匀概率的结果来强制获得答案，否则你需要正式地推理条件概率。 - Gene

“随机选择一个有效的桶”的问题在于，正如您所说，这样做会导致很高的概率找不到解决方案。我正在考虑一种解决方案，即将容器中的项目复制到一个数组中，对其进行随机化，然后使用确定性算法填充桶。 - Jim Mischel

Answer 1

这是一个O(n^3)时间复杂度的算法（3来自于桶的数量）。我们从草图枚举算法开始，然后提取有效的计数算法，最后展示如何进行抽样。我们使用两个嵌套循环的算法进行枚举。外部循环遍历球。每个球的颜色并不重要，只有它可以放置在某些桶中而不能放置在其他桶中。在每次外部迭代开始时，我们有一个部分解决方案列表（到目前为止考虑到的球的分配）。内部循环是针对部分解决方案的；我们通过以所有有效方式扩展分配来将几个部分解决方案添加到新列表中。（初始列表有一个元素，即空分配。）为了更有效地计算解决方案，我们应用了一种称为动态规划或游程编码的技术，具体取决于你的观察角度。如果两个部分解决方案在每个桶中具有相同的计数（在算法的生命周期内有O(n^3)种可能性），则一个的所有有效扩展也是另一个的有效扩展，反之亦然。我们可以用计数注释列表元素，并且丢弃每个“等价类”的部分解决方案除了一个代表。

最后，为了获得随机样本，我们不是任意选择代表者，而是在合并两个列表条目时，按比例从每一侧的计数中抽取代表者。

Python工作代码（为了简单起见，时间复杂度为O(n^4); 可能存在数据结构改进）。

#!/usr/bin/env python3
import collections
import random


def make_key(buckets, bucket_sizes):
    return tuple(bucket_sizes[bucket] for bucket in buckets)


def sample(balls, final_bucket_sizes):
    buckets = list(final_bucket_sizes)
    partials = {(0,) * len(buckets): (1, [])}
    for ball in balls:
        next_partials = {}
        for count, partial in partials.values():
            for bucket in ball:
                next_partial = partial + [bucket]
                key = make_key(buckets, collections.Counter(next_partial))
                if key in next_partials:
                    existing_count, existing_partial = next_partials[key]
                    total_count = existing_count + count
                    next_partials[key] = (total_count, existing_partial if random.randrange(total_count) < existing_count else next_partial)
                else:
                    next_partials[key] = (count, next_partial)
        partials = next_partials
    return partials[make_key(buckets, final_bucket_sizes)][1]


def test():
    red = {'A', 'C'}
    green = {'B', 'C'}
    blue = {'A', 'B'}
    purple = {'B'}
    balls = [red] * 8 + [green] * 8 + [blue] * 8 + [purple] * 4
    final_bucket_sizes = {'A': 7, 'B': 11, 'C': 10}
    return sample(balls, final_bucket_sizes)


if __name__ == '__main__':
    print(test())

- David Eisenstat

---

我正在处理我的伪代码，你突然打断了我，这可让我白忙活了一个小时 :o - 88877

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - beauxq

Answer 2

1 首先，在28个数字中选择7个：你有C28,7=1184040种可能性。

2 其次，在剩下的21个数字中选择11个：你有C21,11=352716种可能性。

3 剩下的10个元素在桶C中。

每一步，如果你的选择不符合规则，你就停止并重新选择。

总共有417629852640种可能性（没有限制的情况下）。

这不是非常高效，但对于一个选择来说，影响不大。如果限制不是太严格，你不会浪费太多时间。

如果解决方案很少，你必须限制组合（只选好的颜色）。

- guillaume girod-vitouchkina

Answer 3

在某些情况下，我们可以通过先使用限制条件将问题缩小到可管理的范围，然后搜索解空间来相当快速地解决这个问题。

首先，注意到我们可以忽略算法的主要部分中球的不同性质。只考虑颜色就找到了解决方案，随机在每种颜色内进行混排即可轻松分配不同编号的球。

为了重述问题并澄清等概率的概念，这里提供了一个天真但简单正确且可能非常低效的算法：

• 将球以均匀概率排序成某个随机顺序。每个n!个排列是等可能的。这可以使用众所周知的洗牌算法完成。
• 按容量顺序将球分配到桶中。换句话说，对于示例桶，首先7个放到A，接着11个放到B，最后10个放到C。
• 检查颜色约束是否已满足。如果没有，则返回到开头；否则停止。

这个样本来自于所有排列的空间，每个排列的概率相等，并过滤掉不符合约束条件的排列，以满足均匀概率。然而，如果给定的约束条件相当严格，它可能会循环数百万次才能找到解决方案。另一方面，如果问题不是非常受限制，它将很快找到解决方案。

我们可以通过首先检查约束条件和每种颜色的球的数量来利用这两个事实。例如，考虑以下内容：

• A：7个球；允许的颜色（红色，蓝色）
• B：11个球；允许的颜色（绿色，蓝色，紫色）
• C：10个球；允许的颜色（红色，绿色）
• 球：6个红色，6个绿色，10个蓝色，6个紫色

在这些参数下进行试验时，朴素算法在2000万次迭代内未能找到有效的解决方案。但现在让我们减少问题。

请注意，所有6个紫色球必须放入B中，因为它是唯一可以接受它们的桶。因此，问题简化为：

• 预分配：B 中有 6 个紫色球
• A：7 个球；允许的颜色（红色，蓝色）
• B：5 个球；允许的颜色（绿色，蓝色）
• C：10 个球；允许的颜色（红色，绿色）
• 球：6 个红色，6 个绿色，10 个蓝色

C 需要 10 个球，只能取红色和绿色。每种颜色都有 6 个。可能的组合是 4+6、5+5、6+4。因此，我们必须在 C 中至少放入 4 个红色和 4 个绿色。

• 预分配：B 中有 6 个紫色球，C 中有 4 个红色球，4 个绿色球
• A：7 个球；允许的颜色（红色，蓝色）
• B：5 个球；允许的颜色（绿色，蓝色）
• C：2 个球；允许的颜色（红色，绿色）
• 球：2 个红色，2 个绿色，10 个蓝色

我们需要把10个蓝球放在某个地方。C不会拿走任何一个。B最多可以拿5个；其余的5个必须放在A中。A最多可以拿7个；其余的3个必须放在B中。因此，A必须至少拿5个蓝色，B必须至少拿3个蓝色。

预分配：B中有6个紫色，C中有4个红色，4个绿色，A中有5个蓝色，B中有3个蓝色

A：2个球；允许颜色（红色，蓝色）

B：2个球；允许颜色（绿色，蓝色）

C：2个球；允许颜色（红色，绿色）

球：2个红色，2个绿色，2个蓝色

此时，问题变得微不足道：检查简化问题的随机解决方案将在几次尝试内找到有效的解决方案。

对于完全简化的问题，720个排列中有80个是有效的，因此可以以1/9的概率找到有效解。对于原始问题，28！个排列中有7！* 11！* 10！* 80个有效解，而找到其中一个的概率小于五十亿分之一。

将上述人类推理转化为简化算法更加困难，我只会简要地考虑它。从上面的具体情况进行概括：

- 是否有任何球只能放入一个桶中？ - 是否有一个桶必须接受某些颜色的最小数量的球？ - 是否有一种颜色只能放入某些桶中？

如果这些方法不能充分简化特定问题，则检查问题可能会产生其他可编码的简化方法。

最后：这种方法总是有效吗？很难确定，但我认为在大多数情况下会有效，因为约束条件是导致朴素算法失败的原因。如果我们可以利用这些约束条件将问题简化为约束条件不太重要的问题，那么朴素算法应该能够轻松找到解决方案；有效解决方案的数量应该是所有可能性的相当大的一部分。

顺便说一句：同样的简化技巧也会提高其他答案的性能，前提是它们是正确的。

- Tom Zych

Answer 4

我不太确定您在随机、正确和有效分配之间想要的权衡是什么。

如果您想要完全随机的分布，只需选择一个球并将其随机放入一个可以放置的桶中即可。这样会非常高效，但您可能很容易让一个桶溢出。

如果您想确保正确和随机，可以尝试获取所有可能的正确分布，并随机选择其中一个，但这可能非常低效，因为创建所有分布可能性的基本暴力算法几乎会达到NumberOfBucket^NumberOfBalls的复杂度。

创建所有正确情况的更好算法是尝试按颜色逐个构建验证您的两个规则（桶B1只能有N1个球和桶只接受某些颜色）的所有情况。例如：

//let a distribution D be a tuple N1,...,Nx of the current number of balls each bucket can accept

void DistributeColor(Distribution D, Color C) {
  DistributeBucket(D,B1,C);
}

void DistributeBucket(Distribution D, Bucket B, Color C) {
  if B.canAccept(C) {
    for (int i = 0; i<= min(D[N],C.N); i++) {
      //we put i balls of the color C in the bucket B
      C.N-=i;
      D.N-=i;
      if (C.N == 0) {
        //we got no more balls of this color
        if (isLastColor(C)){
          //this was the last color so it is a valid solution
          save(D);
        } else {
          //this was not the last color, try next color
          DistributeColor(D,nextColor(C))
        }
      } else {
        //we still got balls
        if (isNotLastBucket(B)) {
          //This was not the last bucket let's try to fill the next one
          DistributeBucket(D, nextBucket(B), C)  
        } else {
          //this was the last bucket, so this distibution is not a solution. Let's do nothing (please don't kill yourself :/ )
        }
      }
      //reset the balls for the next try
      C.N+=i;
      D.N+=i;
    }
  }
  //it feel like déjà vu
  if (isNotLastBucket(B)) {
    //This was not the last bucket let's try to fill the next one
    DistributeBucket(D, nextBucket(B), C)  
  } else {
    //this was the last bucket, so this distribution is not a solution.
  }
}

（这段代码是伪C++代码，不能直接运行）

- 88877