1

我有一个 4x4 2D 字符数组，如下所示：

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

现在，我需要找到 3 个字符、4 个字符等的所有排列，直到 10。

因此，人们可以从中“找到”的一些词是TEN, BALD, BLUE, GUYS。

我确实搜索过这个并用谷歌搜索，但没有具体的帮助。你能把我推向我应该学习哪种算法的正确方向（也许是 A*？）。请温柔一点，因为我不是算法专家（我们不是所有人（好吧，至少是大多数人:)），但我愿意学习，只是不知道从哪里开始。

4

3 回答 3

2

啊，这就是 Boggle 游戏，不是吗...您不想要排列，您想要一个图表，并且您想要在图表中找到单词。

好吧，我首先将字符排列为图形节点，然后将它们连接到它们的直接和对角线邻居。

现在您只想搜索图表。对于 16 个起始节点中的每一个，您将进行递归。当您移动到一个新节点时，您必须将其标记为已使用，这样您就不能再次移动到它。当您离开一个节点（已完全搜索它）时，您取消标记它。

我希望你看到这是怎么回事......

对于每个节点，您将访问其每个邻居并将该字符添加到字符串中。如果您在构建字典时考虑到了这种搜索，您将立即能够查看到目前为止的字符是否是单词的开头。这很好地缩小了搜索范围。

我正在谈论的那种字典是你有一棵树，它的节点对于字母表的每个字母都有一个孩子。这些的美妙之处在于您只需要在搜索中存储您当前正在搜索的树节点。如果您确定找到了一个单词，您只需通过父节点回溯以找出它是哪个单词。

使用这种树样式以及深度优先的图形搜索，您可以同时搜索所有可能的词长。这是我能想到的最有效的方法。

让我为您的图形搜索编写一个伪编码函数：

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

剩下的就是构建图形和字典。我只记得那个字典数据结构叫什么！这是一个特里。如果您需要更节省空间的存储，您可以压缩成Radix Tree或类似的，但到目前为止，最简单（也是最快）的就是使用直接 Trie。

于 2013-01-16T15:24:16.617 回答
2

由于您没有定义我在 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 更改为所需的文本长度。

于 2013-01-16T15:43:05.517 回答
0

看来您只是将 4x4 矩阵用作长度为 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。

每次，您“猜测”下一个要放置的字符 - 并将其附加到候选者，然后递归调用以查找下一个候选者。
对所有可能的猜测重复该过程。

注意有choose(10,16)*10！+ 选择(9,16)*9！+ ... + 选择(3,16)*3！不同的这种排列，所以它可能很耗时......

如果您想要有意义的单词，您将需要某种字典（或从某些上下文中统计地提取一个），以便将候选者与“真实单词”相匹配。

于 2013-01-16T15:21:19.820 回答