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個字符數組中的字符組合：

回答

相關問題