具有约束的随机分布对象的算法
algorithm for randomly distributing objects with constraints
帮我找个好的算法？
我有一袋子装满了n个球。 （以 28 个球为例。）
这个袋子里的球各有 1 种颜色。袋子里有 <= 4 种不同颜色的球。 （假设红色、绿色、蓝色和紫色都是可能的。）
我有三个桶，每个桶都有一个数字，表示他们最终需要多少个球。这些数字总计 n。 （例如，假设 A 桶最终需要 7 个球，B 桶最终需要 11 个球，C 桶最终需要 10 个球。）
桶也可能有也可能没有颜色限制——它们不接受的颜色。 （A桶不接受紫球和绿球。B桶不接受红球。C桶不接受紫球和蓝球。）
我需要高效且随机地分配球（所有可能性的概率均等）。
我不能只是随机地将球放入有 space 的桶中来接受它们，因为这可能会让我陷入这样一种情况，即唯一一个有 space 的桶没有接受袋子里剩下的唯一颜色。
假设总有至少一种分配球的可能性。 （我不会有一袋只有红球的袋子，一些编号 > 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.
这是一个 O(n^3) 时间的算法。 （3 来自桶的数量。）
我们首先勾勒出一个 brute-force 枚举算法，然后提取一个有效的计数算法，然后展示如何采样。
我们用一个有两个嵌套循环的算法来枚举。外循环遍历球。每个球的颜色无关紧要；只是它可以放在某些桶中，而不能放在其他桶中。在每次外部迭代开始时，我们都有一个部分解决方案列表（将到目前为止考虑的球分配给桶）。内部循环是部分解决方案；我们通过以所有有效方式扩展分配，将几个部分解决方案添加到新列表中。 （初始列表只有一个元素，即空赋值。）
为了更有效地计算解决方案，我们应用了一种称为动态规划或 run-length 编码的技术，具体取决于您如何看待它。如果两个部分解决方案在每个存储桶中具有相同的计数（算法生命周期内的 O(n^3) 种可能性），则其中一个的所有有效扩展都是另一个的有效扩展，反之亦然。我们可以用一个计数来注释列表元素，并丢弃除每个 "equivalence class" 部分解决方案的一个代表之外的所有元素。
最后，为了获得随机样本，而不是任意选择代表，当我们合并两个列表条目时，我们从每一侧的代表中按比例对每一侧的代表进行抽样。
工作 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())
我不太确定你想要在随机、正确和有效的分布之间做出什么权衡。
如果你想要一个完全随机的分布，只需挑选一个球并将其随机放入一个桶中，它就可以进去。这会非常有效，但你可能很容易使桶溢出。
如果你想确保是正确的和随机的，你可以尝试让所有可能的分布都是正确的并随机选择其中之一，但它可能非常低效，因为创建所有分布可能性的基本暴力算法会几乎处于 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++，不可运行）
1首先你在28中选择7：你有C28，7=1184040种可能。
2其次，你在剩下的21个中选择11个：你有C21,11=352716种可能。
剩余 10 个元素在 C 桶中。
在每一步中，如果您的选择不符合规则，您就停下来重新做。
一切都有 417629852640 种可能性（无限制）。
效率不是很高，但是对于一个选择，影响不大。如果限制不是太限制，你不会浪费太多时间。
如果解决方案很少，则必须限制组合（仅限好的颜色）。
至少在某些情况下，这个问题可以很快解决
首先使用约束将问题减少到更易于管理的程度
大小，然后搜索解决方案 space.
首先，请注意我们可以忽略球的不同之处
算法的主要部分。找到解决方案后仅考虑
颜色，为每种颜色随机分配不同的球编号是微不足道的
通过在每种颜色内洗牌。
为了重述问题并澄清等概率的概念，这里
是一种朴素的算法，它简单且正确，但可能非常
低效：
- 以均匀的概率将球按随机顺序排序。每个
的！排列的可能性相同。这可以用
well-known 改组算法。
- 根据容量顺序将球分配到桶中。在
换句话说，使用示例桶，第一个 7 到 A，接下来 11 个到 B，
最后 10 名到 C.
- 检查是否满足颜色限制。如果他们没有
遇见，回到原点；否则停止。
这从所有排列的 space 中以等概率采样
并过滤掉不符合约束条件的，所以统一
概率满足。然而，考虑到即使是中度严重
约束，它可能会循环数百万次才能找到
解决方案。另一方面，如果问题不是很受限，它
会很快找到解决办法。
我们可以通过首先检查约束来利用这两个事实
以及每种颜色的球数。例如，考虑
以下：
- 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。所以我们必须至少放 4 个红色和
4 绿色在 C.
- 预分配：B 中 6 个紫色，C 中 4 个红色，C 中 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 个红色，C 中有 4 个绿色，A 中有 5 个蓝色，B 中有 3 个蓝色
- A：2个球；允许的颜色（红色、蓝色）
- B：2个球；允许的颜色（绿色、蓝色）
- C：2个球；允许的颜色（红色、绿色）
- 球：2 个红色、2 个绿色、2 个蓝色
在这一点上，问题很简单：检查随机解决方案
减少的问题将在几次尝试中找到有效的解决方案。
对于fully-reduced问题，720个排列中有80个是有效的，所以
将以 1/9 的概率找到有效的解决方案。对于原来的
问题，满分28！排列有7个！ * 11！ * 10！ * 80 有效
解决方案，找到一个的概率小于五分之一
十亿
把上面用到的人为推理变成归约算法更
很难，我只会简单地考虑一下。从
以上具体案例：
- 是否有任何球只能进入一个桶？
- 是否有一个桶必须装一些最小数量的球
还是更多颜色？
- 是否有一种颜色只能进入特定的桶？
如果这些不能充分减少特定问题，检查
该问题可能会产生其他减少，然后可以对其进行编码。
最后：这会一直有效吗？很难确定，但我怀疑
在大多数情况下，它会，因为约束是导致天真的原因
算法失败。如果我们可以使用约束来减少问题
对于约束无关紧要的算法，朴素算法
应该找到一个没有太多麻烦的解决方案；有效数量
解决方案应该是所有的相当大的一部分
可能性。
事后思考：同样的减少技术会提高性能
在这里的其他答案中，to，假设他们是正确的。
帮我找个好的算法？
我有一袋子装满了n个球。 （以 28 个球为例。）
这个袋子里的球各有 1 种颜色。袋子里有 <= 4 种不同颜色的球。 （假设红色、绿色、蓝色和紫色都是可能的。）
我有三个桶，每个桶都有一个数字，表示他们最终需要多少个球。这些数字总计 n。 （例如，假设 A 桶最终需要 7 个球，B 桶最终需要 11 个球，C 桶最终需要 10 个球。）
桶也可能有也可能没有颜色限制——它们不接受的颜色。 （A桶不接受紫球和绿球。B桶不接受红球。C桶不接受紫球和蓝球。）
我需要高效且随机地分配球（所有可能性的概率均等）。
我不能只是随机地将球放入有 space 的桶中来接受它们，因为这可能会让我陷入这样一种情况，即唯一一个有 space 的桶没有接受袋子里剩下的唯一颜色。
假设总有至少一种分配球的可能性。 （我不会有一袋只有红球的袋子，一些编号 > 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.
这是一个 O(n^3) 时间的算法。 （3 来自桶的数量。）
我们首先勾勒出一个 brute-force 枚举算法，然后提取一个有效的计数算法，然后展示如何采样。
我们用一个有两个嵌套循环的算法来枚举。外循环遍历球。每个球的颜色无关紧要；只是它可以放在某些桶中，而不能放在其他桶中。在每次外部迭代开始时，我们都有一个部分解决方案列表（将到目前为止考虑的球分配给桶）。内部循环是部分解决方案；我们通过以所有有效方式扩展分配，将几个部分解决方案添加到新列表中。 （初始列表只有一个元素，即空赋值。）
为了更有效地计算解决方案，我们应用了一种称为动态规划或 run-length 编码的技术，具体取决于您如何看待它。如果两个部分解决方案在每个存储桶中具有相同的计数（算法生命周期内的 O(n^3) 种可能性），则其中一个的所有有效扩展都是另一个的有效扩展，反之亦然。我们可以用一个计数来注释列表元素，并丢弃除每个 "equivalence class" 部分解决方案的一个代表之外的所有元素。
最后，为了获得随机样本，而不是任意选择代表，当我们合并两个列表条目时，我们从每一侧的代表中按比例对每一侧的代表进行抽样。
工作 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())
我不太确定你想要在随机、正确和有效的分布之间做出什么权衡。
如果你想要一个完全随机的分布，只需挑选一个球并将其随机放入一个桶中，它就可以进去。这会非常有效，但你可能很容易使桶溢出。
如果你想确保是正确的和随机的，你可以尝试让所有可能的分布都是正确的并随机选择其中之一，但它可能非常低效，因为创建所有分布可能性的基本暴力算法会几乎处于 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++，不可运行）
1首先你在28中选择7：你有C28，7=1184040种可能。
2其次，你在剩下的21个中选择11个：你有C21,11=352716种可能。
剩余 10 个元素在 C 桶中。
在每一步中，如果您的选择不符合规则，您就停下来重新做。
一切都有 417629852640 种可能性（无限制）。
效率不是很高，但是对于一个选择，影响不大。如果限制不是太限制，你不会浪费太多时间。
如果解决方案很少，则必须限制组合（仅限好的颜色）。
至少在某些情况下，这个问题可以很快解决 首先使用约束将问题减少到更易于管理的程度 大小，然后搜索解决方案 space.
首先，请注意我们可以忽略球的不同之处 算法的主要部分。找到解决方案后仅考虑 颜色，为每种颜色随机分配不同的球编号是微不足道的 通过在每种颜色内洗牌。
为了重述问题并澄清等概率的概念，这里 是一种朴素的算法，它简单且正确，但可能非常 低效：
- 以均匀的概率将球按随机顺序排序。每个 的！排列的可能性相同。这可以用 well-known 改组算法。
- 根据容量顺序将球分配到桶中。在 换句话说，使用示例桶，第一个 7 到 A，接下来 11 个到 B， 最后 10 名到 C.
- 检查是否满足颜色限制。如果他们没有 遇见，回到原点；否则停止。
这从所有排列的 space 中以等概率采样 并过滤掉不符合约束条件的，所以统一 概率满足。然而，考虑到即使是中度严重 约束，它可能会循环数百万次才能找到 解决方案。另一方面，如果问题不是很受限，它 会很快找到解决办法。
我们可以通过首先检查约束来利用这两个事实 以及每种颜色的球数。例如，考虑 以下：
- 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。所以我们必须至少放 4 个红色和 4 绿色在 C.
- 预分配：B 中 6 个紫色，C 中 4 个红色，C 中 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 个红色，C 中有 4 个绿色，A 中有 5 个蓝色，B 中有 3 个蓝色
- A：2个球；允许的颜色（红色、蓝色）
- B：2个球；允许的颜色（绿色、蓝色）
- C：2个球；允许的颜色（红色、绿色）
- 球：2 个红色、2 个绿色、2 个蓝色
在这一点上，问题很简单：检查随机解决方案 减少的问题将在几次尝试中找到有效的解决方案。
对于fully-reduced问题，720个排列中有80个是有效的，所以 将以 1/9 的概率找到有效的解决方案。对于原来的 问题，满分28！排列有7个！ * 11！ * 10！ * 80 有效 解决方案，找到一个的概率小于五分之一 十亿
把上面用到的人为推理变成归约算法更 很难，我只会简单地考虑一下。从 以上具体案例：
- 是否有任何球只能进入一个桶？
- 是否有一个桶必须装一些最小数量的球 还是更多颜色？
- 是否有一种颜色只能进入特定的桶？
如果这些不能充分减少特定问题，检查 该问题可能会产生其他减少，然后可以对其进行编码。
最后：这会一直有效吗？很难确定，但我怀疑 在大多数情况下，它会，因为约束是导致天真的原因 算法失败。如果我们可以使用约束来减少问题 对于约束无关紧要的算法，朴素算法 应该找到一个没有太多麻烦的解决方案；有效数量 解决方案应该是所有的相当大的一部分 可能性。
事后思考：同样的减少技术会提高性能 在这里的其他答案中，to，假设他们是正确的。