一种尝试无反馈分组的算法
An algorithm for grouping by trying without feedback
将此标记为 Python 因为在我看来这是最 伪 y 代码 的语言
我会用图形来解释，答案也可以是 graphical/theorical（也许 post 这个网站错了？）
假设我想制作一个算法来解决一个简单的婴儿数字游戏（这不是实际情况，它要复杂得多）
规则如下：
从上面看是一个正方形的网格，里面有一个彩色的乐高积木
每个点
您可以拖动碎片来尝试堆叠在一起。
如果他们的颜色匹配，他们将叠加，留下第一个的位置
你拖空的一块。
如果你把一个棋子移到一个空位，它也会移动到那个位
如果它们的颜色不匹配并且您将一个拖到另一个的顶部，它们
会换位置。
相同颜色的棋子数量是在新的格子开始时随机生成的。
游戏的目标显然是拖动相同颜色的棋子，直到每种颜色只有一堆。
现在问题来了，我想制作一个解决游戏的脚本，但它会是 "blind"，这意味着它无法看到颜色，也无法跟踪匹配发生的时间。它必须以确保尝试所有可能的方式遍历 "drags"
我什至开始考虑这个问题的主要问题是，如果脚本猜不出颜色，他们就会交换位置，而且没有反馈知道你猜错了。
还有这个复杂度是可以计算的吗？是不是太疯狂了？
让我们尝试以下操作：
假设我们有一个 m 乘以 n 的网格，有 p 种不同的颜色。首先，我们使用以下算法逐行处理：
列减少
- 将 (1,1) 处的棋子拖动到 (1,2)，然后将 (1,2) 拖动到 (1,3) 等等，直到到达 (1, n)
- 将 (1,1) 处的棋子以同样的方式拖动到 (1,n-1)。
- 继续，直到移动到 (1, n-p) 为止。
第一步保证将原先在(1,1)的颜色移动到(1,n)，并在途中收集所有相同颜色的棋子。
后续步骤收集剩余的颜色。在算法的这一部分之后，我们保证只填充 p 到 n 列，每一列都有不同的颜色。
我们对剩余的 m-1 行重复此操作。之后，第 1 列到 n-p-1 列保证为空。
行减少
现在我们对列重复相同的过程，即将所有 j >= n-p 的 (1, j) 拖到 (m, j)，然后将 (1,j) 拖到 (m-1, j) .
在这部分之后，我们保证只填充了 p 次 p 子网格。
全格搜索
现在我们通过暴力收集各种不同的颜色：
将 (p,p) 移动到 (p,p+1), (p, p+2), ... (p, n) 然后移动到 (p + 1, n), (p+1, n-1 ), ..., (p+1, p) 然后到 (p+2, p), ..., (p+2, n) 等等，直到我们到达 (m, p) 或 (m ,n), 取决于 p 是偶数还是奇数。
这个步骤我们重复p次，只是我们每次都在最后一个短的字段上停止。
因此，只有剩余的 p 个字段被填充，并且每个字段都包含相同颜色的堆栈。问题已解决。
估计复杂度：
- 行移动部分需要n + n-1 + n-2 + ... + n-p= n*(n+1)/2 - (n-p)*(n-p+1)/2= np+(p^2+p)/2=O(n^2) 每行移动，因此 O(mn^2).
- 列移动部分同样需要 O(nm^2) 次移动。
- 最终走法需要对每种颜色走p^2步，即O(p^3)。
如果 q = max(n,m,p) 复杂度为 O(q^3)。
注意：如果我们不知道 p 我们可以立即开始全网格搜索。我们仍然保持复杂度 O(q^3)。但是，如果 p << n 或 p << m，列和行的减少将大大降低实际的复杂性。
将此标记为 Python 因为在我看来这是最 伪 y 代码 的语言
我会用图形来解释，答案也可以是 graphical/theorical（也许 post 这个网站错了？）
假设我想制作一个算法来解决一个简单的婴儿数字游戏（这不是实际情况，它要复杂得多）
规则如下：
从上面看是一个正方形的网格，里面有一个彩色的乐高积木 每个点
您可以拖动碎片来尝试堆叠在一起。
如果他们的颜色匹配，他们将叠加，留下第一个的位置 你拖空的一块。
如果你把一个棋子移到一个空位，它也会移动到那个位
如果它们的颜色不匹配并且您将一个拖到另一个的顶部，它们 会换位置。
相同颜色的棋子数量是在新的格子开始时随机生成的。
游戏的目标显然是拖动相同颜色的棋子，直到每种颜色只有一堆。
现在问题来了，我想制作一个解决游戏的脚本，但它会是 "blind"，这意味着它无法看到颜色，也无法跟踪匹配发生的时间。它必须以确保尝试所有可能的方式遍历 "drags"
我什至开始考虑这个问题的主要问题是，如果脚本猜不出颜色，他们就会交换位置，而且没有反馈知道你猜错了。
还有这个复杂度是可以计算的吗？是不是太疯狂了？
让我们尝试以下操作：
假设我们有一个 m 乘以 n 的网格，有 p 种不同的颜色。首先，我们使用以下算法逐行处理：
列减少
- 将 (1,1) 处的棋子拖动到 (1,2)，然后将 (1,2) 拖动到 (1,3) 等等，直到到达 (1, n)
- 将 (1,1) 处的棋子以同样的方式拖动到 (1,n-1)。
- 继续，直到移动到 (1, n-p) 为止。
第一步保证将原先在(1,1)的颜色移动到(1,n)，并在途中收集所有相同颜色的棋子。 后续步骤收集剩余的颜色。在算法的这一部分之后，我们保证只填充 p 到 n 列，每一列都有不同的颜色。
我们对剩余的 m-1 行重复此操作。之后，第 1 列到 n-p-1 列保证为空。
行减少
现在我们对列重复相同的过程，即将所有 j >= n-p 的 (1, j) 拖到 (m, j)，然后将 (1,j) 拖到 (m-1, j) .
在这部分之后，我们保证只填充了 p 次 p 子网格。
全格搜索
现在我们通过暴力收集各种不同的颜色： 将 (p,p) 移动到 (p,p+1), (p, p+2), ... (p, n) 然后移动到 (p + 1, n), (p+1, n-1 ), ..., (p+1, p) 然后到 (p+2, p), ..., (p+2, n) 等等，直到我们到达 (m, p) 或 (m ,n), 取决于 p 是偶数还是奇数。
这个步骤我们重复p次，只是我们每次都在最后一个短的字段上停止。
因此，只有剩余的 p 个字段被填充，并且每个字段都包含相同颜色的堆栈。问题已解决。
估计复杂度：
- 行移动部分需要n + n-1 + n-2 + ... + n-p= n*(n+1)/2 - (n-p)*(n-p+1)/2= np+(p^2+p)/2=O(n^2) 每行移动，因此 O(mn^2).
- 列移动部分同样需要 O(nm^2) 次移动。
- 最终走法需要对每种颜色走p^2步，即O(p^3)。
如果 q = max(n,m,p) 复杂度为 O(q^3)。
注意：如果我们不知道 p 我们可以立即开始全网格搜索。我们仍然保持复杂度 O(q^3)。但是，如果 p << n 或 p << m，列和行的减少将大大降低实际的复杂性。