n个字符数组中的字符组合：

首先注意：对不起，我的图像没有分开。我是一名新成员，所以我没有足够的声望点发布超过一个超链接。n个字符数组中的字符组合：

设M是n乘n阵列（数学方阵）的字符。

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

下面显示了不可接受的置换。

我已经得出这么多：

的对号可以有至多为n的平方内的字符（如没有字符可以重复）。
我不知道给定限制的置换的确切数量，但我相信不能超过通过评估超链接中描述的表达式所产生的值。

我可以很容易地找到只包含直线字符的排列：垂直线，水平线和对角线。我不确定如何彻底查找所有剩余的排列。

我已经完成了研究并且还找不到类似问题的解决方案。

任何意见，在开发这样的穷举算法将不胜感激。

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

来源

2011-02-01 Zéychin

是“组合”矩阵中元素的有序序列，还是仅仅是矩阵中的一组元素？ – 2011-02-01 02:59:22

一种算法想到马上，虽然优化可以进行，如果时间复杂性是一个问题。

在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）搜索）的新字母的包含，则该算法的最坏情况运行时复杂度在数量上是线性的矩阵中有可能的字符串。即如果矩阵中有n个可能的字符串组合，那么这个算法需要大约n个步骤才能完成，其中c是一个常数。

来源

2011-02-01 03:17:31 Olhovsky

n个字符数组中的字符组合：

回答

相关问题