4x4的2D人物矩陣排列

Question

我有字符的4×4二維數組是這樣的：

A B C D 
U A L E 
T S U G 
N E Y I 

現在，我需要找到的3個字符，4個字符，等所有的排列，直到10

因此，可以從中找到的一些詞是TEN,BALD,BLUE,GUYS。

我確實搜索過這個和谷歌搜索，但沒有具體的幫助。你能把我推向正確的方向嗎？我應該學習哪種算法（A *也許？）。請溫柔一點，因爲我不算算算傢伙（不是我們全部（好吧，至少是大多數:)），但是我願意學習只是不知道從哪裏開始。

Answer 1

啊，這就是遊戲Boggle是不是...你不想排列，你想要一個圖，你想在圖中找到單詞。

那麼，我首先將字符排列爲圖形節點，然後將它們連接到它們的直接鄰居和對角線鄰居。

現在你只是想搜索圖表。對於16個起始節點中的每一個，您都要進行遞歸。在移動到新節點時，必須將其標記爲正在使用，以便您不能再移動到該節點。當你離開一個節點（完全搜索它）時，你將它解除標記。

我希望你看這是怎麼回事...

對於每個節點，您將參觀各鄰國和字符添加到字符串。如果你已經在腦海中建立了你的字典，那麼你將立刻就能看到你到目前爲止的字符是否是一個字的開頭。這很好地縮小了搜索範圍。

我談論的字典的種類是你有一棵樹的節點每個字母的字母有一個孩子。這些美妙之處在於你只需要在搜索中存儲你現在正在使用的樹節點。如果你決定找到一個單詞，你只需通過父節點回溯，找出它是哪個單詞。

使用此樹樣式以及深度優先圖搜索，您可以同時搜索所有可能的字長。這是我能想到的最有效的方式。

---

讓我寫一個pseudocodish功能，爲您的圖形搜索：

function FindWords(graphNode, dictNode, wordsList) 
    # can't use a letter twice 
    if graphNode.used then return 

    # don't continue if the letter not part of any word 
    if not dictNode.hasChild(graphNode.letter) then return 
    nextDictNode = dictNode.getChild(graphNode.letter) 

    # if this dictionary node is flagged as a word, add it to our list 
    nextDictNode.isWord() 
     wordsList.addWord(nextDictNode .getWord()) 
    end 

    # Now do a recursion on all our neighbours 
    graphNode.used = true 
    foreach nextGraphNode in graphNode.neighbours do 
     FindWords(nextGraphNode, nextDictNode, wordsList) 
    end 
    graphNode.used = false 
end 

和當然，踢了整個事情關閉：

foreach graphNode in graph do 
    FindWords(graphNode, dictionary, wordsList) 
end 

剩下的工作就是建立圖表和字典。我只記得那個字典數據結構叫什麼！這是一個Trie。如果你需要更節省空間的存儲，你可以壓縮成Radix Tree或類似的，但最簡單（最快）的就是使用直接Trie。

Answer 2

看來你只需要使用4×4矩陣長度爲16的數組如果是的話，你可以嘗試遞歸方法來生成排列的最大長度是k如下：

findPermutations(chars, i, highLim, downLim, candidate): 
    if (i > downLim): 
     print candidate 
    if (i == highLim): //stop clause 
     return 
    for j in range(i,length(chars)): 
     curr <- chars[i] 
     candidate.append(curr) 
     swap(chars,i,j) // make it unavailable for repicking 
     findPermutations(chars,i+1,highLim,downLim,candidate) 
     //clean up environment after recursive call: 
     candidate.removeLast() 
     swap(chars ,i, j) 

的想法是打印每個有更多字符的「候選人」，然後downLim（在你的情況下是3），並在達到上限（highLim） - 10時終止。

在每一次，你都會「猜測」下一個字符是什麼 - 然後你將它附加到候選者，並遞歸地調用以找到下一個候選者。
重複所有可能的猜測過程。

請注意，有選擇（10,16）* 10！ +選擇（9,16）* 9！ + ... +選擇（3,16）* 3！不同的這樣的排列，所以它可能是費時......

---

如果你想意味深長的話，你將需要某種形式的詞典（或統計學提取一個從某些方面），以配合具有「真實話語」的候選人。

Answer 3

正如你不能定義我的C＃實現的首選語言：

private static readonly int[] dx = new int[] { 1, 1, 1, 0, 0, -1, -1, -1 }; 
private static readonly int[] dy = new int[] { -1, 0, 1, 1, -1, -1, 0, 1 }; 

private static List<string> words; 
private static List<string> GetAllWords(char[,] matrix ,int d) 
{ 
    words = new List<string>(); 
    bool[,] visited = new bool[4, 4]; 
    char[] result = new char[d]; 

    for (int i = 0; i < 4; i++) 
     for (int j = 0; j < 4; j++) 
      Go(matrix, result, visited, d, i, j); 

    return words; 
} 

private static void Go(char[,] matrix, char[] result, bool[,] visited, int d, int x, int y) 
{ 
    if (x < 0 || x >= 4 || y < 0 || y >= 4 || visited[x, y]) 
     return; 

    if (d == 0) 
    { 
     words.Add(new String(result)); 
     return; 
    } 

    visited[x, y] = true; 
    result[d - 1] = matrix[x, y]; 

    for (int i = 0; i < 8; i++) 
    { 
     Go(matrix, result, visited, d - 1, x + dx[i], y + dy[i]); 
    } 

    visited[x, y] = false; 
} 

代碼，得到的結果：

char[,] matrix = new char[,] { { 'A', 'B', 'C', 'D' }, { 'U', 'A', 'L', 'E' }, { 'T', 'S', 'U', 'G' }, { 'N', 'E', 'Y', 'I' } }; 
    List<string> list = GetAllWords(matrix, 3); 

改變參數3到所需的文本長度。