桌游《达芬奇密码》中概率分布的快速计算

Question

我感兴趣的是，根据棋盘游戏《达芬奇密码》中对手的手（以及您自己的手）可以观察到的情况，有效地计算可能的秘密数字的概率分布。游戏链接：https ://boardgamegeek.com/boardgame/8946/da-vinci-code

我将问题抽象为以下内容：给定一个长度为 N 的数组 A 和数组的每个索引 i 的有限数字 Si 集。现在，

1. 我们将 Si 中的一个数字放置在每个索引 i 处以填充整个数组 A；
2. 同时确保该数字在整个数组 A 中是唯一的；
3. 对于 A 的 3 个不相交子数组 A1、A2、A3，使得 concat(A1, A2, A3) = A，每个子数组中的数字必须遵循严格递增的顺序；给定组成 A 且满足上述约束的所有可能数字，每个索引处每个数字的概率分布是多少？

这里我提供一个例子： 假设我们有以下长度为 5 的数组，每列代表列索引处的 Si

| 6 6 | 6 6 | 6 |
|   5 |   5 |   |
| 4 4 |     | 4 |
|     | 3 3 |   |
| 2   | 2 2 |   |
| 1 1 |     |   | 
| ___ | __  | _ |
| A1  | A2  | A3| 

所有可能的数组的集合为： 14236 14256 14356 15234 15236 15264 15364 16234 16254 16354 24356 25364 26354 45236

因此，每个索引处每个数字 [1-6] 的概率分布为：

 
6 0 4/14 0 3/14 6/14 

5 0 6/14 0 6/14 0     

4 1/14 4/14 0 0 8/14 

3 0 0 6/14 5/14 0     

2 3/14 0 8 /14 0 0     

1 10/14 0 0 0 0     

___________ __________ ______ 

    A1 A2 A3    
 

暴力破解这个问题显然是可行的，但我有一种直觉，必须有一些更有效的算法来解决这个问题。

我之所以这么认为，是因为人们可以从所有可能性的集合中推导出概率分布，但反之则不然，因此分布本身包含的信息必须少于所有可能性的集合所包含的信息。因此，我认为我们不需要仅仅为了获得概率分布而生成所有可能性。

因此，我想知道是否有任何智能矩阵运算可以用于解决这个问题，甚至可以使用定点迭代/密度演化来近似最终概率分布？还赞赏解决此问题的其他一些可能更有效的方法。

编辑：通过暴力，我的意思是专门枚举具有约束传播的所有可能性，就像数独一样。我的希望是获得一个准确的解决方案，或者一个近似的近似解决方案（比普通蒙特卡罗更好），在运行时间方面比 CP 效果更好。

Edit2：我想要的更好的解决方案应该具有不需要生成所有可能性来获得或近似概率分布的特点。

Answer 1

获得分布近似值的一个简单想法是使用蒙特卡罗方法。

设置一个变量total: = 0和一个矩阵M[N][Q]，所有条目最初设置为零（Q是允许的数字总数）。

固定一个正整数K。执行K迭代。在每次迭代中，对于每个iin [1..N]，从 中取出一个随机元素Si并填充数组A。当数组A全部填满后，验证O(N)它是否满足您的条件。如果是，则将变量加一并total迭代数组，将矩阵条目加M[i][A[i]]一，对于iin [1..N]。

最后，迭代矩阵M中的所有元素O(N Q)并将其元素除以total得到分布的近似值。

总时间复杂度为O(N (K + Q))。

您还可以预先计算一些内容以使近似值更加精确。例如，您可以预先计算组A1、A2和中的所有递增序列A3。将它们放入数组I1, I2, I3。Si然后，在每次迭代中，您不是从每个 中获取随机元素，而是从 中获取随机序列I1，I2并I3验证串联是否没有重复元素（在 中O(N)）。如果是这样，请像以前一样进行。总时间复杂度（除了昂贵的预先计算）仍然是O(N (K + Q))。