谷歌google跪经

zzgzzm 发表于 2016-11-25 08:52
我也是这么想的，但算法bias在于前2个格子是完全自由度的，但第3个格子的概率分布又依赖于前2个格子的can ...

我感觉你说的蛮有道理……可是我有点转不过来……我之前计算过 每个格子放任何一个数字的概率是1/n，为啥到最后会变成概率不一样呢……求解答下……

chengbaokun 发表于 2016-11-27 13:14
我感觉你说的蛮有道理……可是我有点转不过来……我之前计算过 每个格子放任何一个数字的概率是1/n，为啥 ...

这就是因为顺序造成的。“每个格子任意以1/4概率随机生成”只能用与前两个格子，从第三个开始就不能这样了。就用最简单的3x1棋盘（4种糖果）:头两个格子生成结果为“1，1”或“1，2”的概率各为1/16。那么第三个格子生成3的概率是不一样的。在“1，1”情况下以1/3生成3，但在“1，2”情况下以1/4生成3，导致最终“113”和“123”棋盘的概率是不同的，这纯粹是由算法设计是从左向右逐个格子进行导致的。若换个方向的话这两个棋盘概率相同，但还是有其它棋盘概率不同。总之这种按贪心算法逐个格子考虑进行概率生成的无法预见棋盘整体的pattern.

zzgzzm 发表于 2016-11-27 15:48
这就是因为顺序造成的。“每个格子任意以1/4概率随机生成”只能用与前两个格子，从第三个开始就不能这样 ...

我有些不一样的想法，麻烦你看下这样对么。

假设有三种颜色，3X1的board 。

第一个和第二个不管选什么颜色都是1/3。现在我们来看第三个格子放置棋子1的概率。

((2,2)(3,3))*1/2+((1,3),(1,2),(2,3),(2,1),(3,1),(3,3))*1/3 =2/9*1/2+6/9*1/3=1/3

扩展到更多的格子，我算了一下，概率也都是等同的。这就意味在这个假设下不管是什么pattern，都是1／27的概率生成。

现在的问题是，只有24种有效结果，怎么会是1/27呢。我觉得这是一个条件概率问题。

P(pattern/valid) = (1/27)/(24/27)=1/24

chengbaokun 发表于 2016-11-27 23:46
我有些不一样的想法，麻烦你看下这样对么。

假设有三种颜色，3X1的board 。

X3=1的概率为1/3没有问题。其实这个无需计算就可以用轮换对称证明甚至对于NxN棋盘，任何X(i,j)=1的概率都是1/3（糖果彼此无bias,但格子顺序有bias)。但是问题的关键在于将几个1/3乘起来做为某个特定组合的概率是不对的，因为按照我们的算法不同的X(i, j)彼此之间不是独立事件。例如112组合中三个事件x1 =1,x2=1,x3=2的概率分别都是1/3，但三件同时发生的概率就不是1/27。乘法原理这里不适用。

zzgzzm 发表于 2016-11-28 09:35
X3=1的概率为1/3没有问题。其实这个无需计算就可以用轮换对称证明甚至对于NxN棋盘，任何X(i,j)=1的概率都 ...

这就相当于对于一个填满的随机valid sudoku 棋盘，任意位置x(i,j)=k的概率均为1/9，但是(1/9)^81显然不是返回一个valid sodoku棋盘的平均概率，因为9^81是整个棋盘随便填满无任何限制的种数，这肯定比valid sudoku 棋盘个数多的多。

zzgzzm 发表于 2016-11-28 09:52
这就相当于对于一个填满的随机valid sudoku 棋盘，任意位置x(i,j)=k的概率均为1/9，但是(1/9)^81显然不是 ...

嗯....请问你这个题的代码是怎么写的啊

chengbaokun 发表于 2016-11-28 13:36
嗯....请问你这个题的代码是怎么写的啊

在之前的层有我post 的随机生成candy crush棋盘C++代码。大体方法为：对行index i 和列index j两层loop从0到N-1, 等概率随机给格子(i，j)合法的糖果，也就是贪心算出当前能有几个糖果选择：若纵向candy(i-2,j)==candy(i-1,j)，排除掉那种糖果；若横向candy(i,j-2)==candy(i,j-1)，再排除；然后在剩下的选择中等概率随机生成一个。这样除了(0，1)(0，2)(1，0)(2，0)外其他格子生成糖果概率事件不是彼此独立的。

zzgzzm 发表于 2016-11-26 04:33
感谢reservoir sampling的提示, 我没想到这样可以避免定义繁琐的options[][]:

不好意思麻烦问下， 能稍微解释下reservoir sampling这块嘛？ 为什么每次是x++，有没有可能最后一步x++后正好等于 vert 或者hor呢？

Roisterer 发表于 2016-11-29 08:59
不好意思麻烦问下， 能稍微解释下reservoir sampling这块嘛？ 为什么每次是x++，有没有可能最后一步x++后 ...

感谢指正！我的确忽略了这一点，没有全面测试   :-(
Line7应该改为:

1.   for (int c = 2; c <= 4; c++) {
   
2.     if (x == hor || x == vert) c = ++x;
   
3.     else if (c != hor && c != vert && !rand()%(++mod)) x = c;
   
4.   }

复制代码

zzgzzm 发表于 2016-11-26 04:33
感谢reservoir sampling的提示, 我没想到这样可以避免定义繁琐的options[][]:

补充内容 (2016-11-30 07: ...

为啥需要水池抽样呀，感觉没必要，糖果总数是确定的n个，然后假如有vert或者hor 就n - 1或者n-2
然后rand() % 一下，如果结果等于vert 或者hor 就代表是 最后两个
sz =  (vert != 0) + (hor != 0);
n -= sz;
res = rand() % n + 1;
if (res == hor) res = (n + 1);
else if (res == vert) res = (n + 1 + (sz == 2))