arrays - n x n 字符数组中的字符组合 :

Question

首先注意:对不起，我的图像没有分开。我是新成员(member)，所以我没有足够的声望点来发布多个超链接。

令 M 为 n × n 字符数组(数学方阵)。

在 M 中，我需要能够找到所有有限制的字符排列。排列不一定是线性的，但它们是 必须包含字符，使得每个字符与排列中的至少一个其他字符相邻。下面是一个可接受的排列示例:

下面显示了一个 Not Acceptable 排列。

我得出了这么多:

一个排列中最多可以有 n 个平方字符(因为没有字符可以重复)。

鉴于限制，我不知道排列的确切数量，但我相信不会超过通过评估超链接中描绘的表达式生成的值。

我可以很容易地找到只包含直线字符的排列:垂直线、水平线和对角线。我不确定是否有办法彻底找到所有剩余的排列。

我进行了研究，但未能找到解决类似问题的方法。

对于开发这种详尽算法的任何建议，我们将不胜感激。

http://i.stack.imgur.com/uDNfv.png

Answer 1

如果时间复杂性是一个问题，尽管可以进行优化，但可以立即想到一种算法。

在 2x2 数组中的每个元素(或者如果您愿意，我们可以将其称为矩阵)，我们可以移动 8 个方向(北、东北、东、东南、南、西南、西、西北)。

算法核心的伪代码有点像这样(我假设按值传递，因此“current_string”在每个函数调用中都是一个新字符串):

find(position, direction, current_string){
    new_letter = m[0, position + direction];
    if(!current_string.Contains(new_letter)){
        // We have not yet encountered this letter during the search.
        // If letters occur more than once in the array, then you must
        // assign an index to each position in the array instead and
        // store which positions have been encountered along each
        // search path instead.
        current_string += new_letter;
        find(position, (0, 1), current_string);
        find(position, (1, 1), current_string);
        find(position, (1, 0), current_string);
        find(position, (1, -1), current_string);
        find(position, (0, -1), current_string);
        find(position, (-1, -1), current_string);
        find(position, (-1, 0), current_string);
        find(position, (-1, 1), current_string);
    } else {
        // This letter has been encountered during this path search,
        // terminate this path search. See comment above if letters
        // occur more than once in the matrix.
        print current_string; // Print one of the found strings!
    }
}

现在您需要添加一些检查，例如“位置+方向是否在数组边界之外，如果是，则打印 current_string 并终止”。

上述算法的高级思想是递归地搜索所有可能的路径，当它们遇到自己时终止路径(就像游戏中的蛇死亡 Snake 一样)。

如果您使用散列来测试新字母对当前字符串的包含情况(根据行 if(!current_string.Contains(new_letter)){ )，这是分期 O(1) 搜索，那么该算法的最坏情况运行时复杂度在可能的数量上是线性的矩阵中有字符串。 IE。如果矩阵中有 n 个可能的字符串组合，那么对于较大的 n，该算法大约需要 cn 步才能完成，其中 c 是某个常数。