4×4二维字符矩阵排列 [英] 4x4 2D character matrix permutations

问题描述

我有字符的4×4二维数组是这样的：

I have a 4x4 2D array of characters like this:

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

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

Now, I would need to find all the permutations of 3 characters, 4 characters, etc till 10.

所以，有些话，人们可以找出了这是 TEN ，秃头， BLUE ， GUYS 。

So, some words that one could "find" out of this are TEN, BALD, BLUE, GUYS.

我的搜索，这和Google搜索，但没有具体的帮助。你可以把我在正确的方向上的算法，我应该学会（A *可能？）。请温柔的我不是算法的人（不是大家（当然，至少大部分:)），但我愿意学习只是不知道在什么地方开始。

I did search SO for this and Googled, but to no concrete help. Can you push me in the right direction in which algorithm I should learn (A* maybe?). Please be gentle as I'm no algorithms guy (aren't we all (well, at least a majority :)), but am willing to learn just don't know where exactly to start.

推荐答案

唉唉，这是本场比赛惊奇是不是......你不想排列，你想有一个图表，你想找到图中的话

Ahhh, that's the game Boggle isn't it... You don't want permutations, you want a graph and you want to find words in the graph.

嗯，我会通过安排字符图形节点开始和他们在一起，他们的直接和对角线邻居。

Well, I would start by arranging the characters as graph nodes, and join them to their immediate and diagonal neighbours.

现在你只是想要搜索的图形。对于每个16出发节点，你打算做一个递归。当你移动到一个新的节点，必须其标记为正在使用，这样就可以不动它了。当你离开一个节点（具有完全搜索到它），你取消标记它。

Now you just want to search the graph. For each of the 16 starting nodes, you're going to do a recursion. As you move to a new node, you must flag it as being used so that you can't move to it again. When you leave a node (having completely searched it) you unflag it.

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

I hope you see where this is going...

对于每个节点，您将参观它的每一个邻国和该字符添加到字符串。如果您已经构建了字典，记此搜索，你会立即能够看到你是否有字符至今是一个单词的起始处。这缩小了搜索很好。

For each node, you will visit each of its neighbours and add that character to a string. If you have built your dictionary with this search in mind, you will immediately be able to see whether the characters you have so far are the beginning of a word. This narrows the search nicely.

本的字典，我说的是，你有树的节点有一个孩子的每个字母。这些的好处是，你只需要存储你目前最多在搜索其树节点。如果你决定你找到一个词，你只要通过父节点回溯到制定出它是哪个单词。

The kind of dictionary I'm talking about is where you have a tree whose nodes have one child for each letter of the alphabet. The beauty of these is that you only need to store which tree node you're currently up to in the search. If you decide you've found a word, you just backtrack via the parent nodes to work out which word it is.

随着深度优先图搜索使用这棵树的风格，你可以在同一时间搜索所有可能的字的长度。这是对最有效的方法我能想到的。

Using this tree style along with a depth-first graph search, you can search ALL possible word lengths at the same time. That's about the most efficient way I can think of.

让我写一个pseudocodish功能，为您图搜索：

Let me just write a pseudocodish function for your graph search:

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

当然，踢了整个事情关闭：

And of course, to kick the whole thing off:

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

剩下的工作就是建立图表和字典。我只记得那是什么意思的数据结构被称为！这是一个特里。如果您需要更多空间，高效的存储，您可以COM preSS成基数树或类似的，但是目前为止最简单的（和最快的）是只用一条直线特里。

All that remains is to build the graph and the dictionary. And I just remembered what that dictionary data structure is called! It's a Trie. If you need more space-efficient storage, you can compress into a Radix Tree or similar, but by far the easiest (and fastest) is to just use a straight Trie.

这篇关于4×4二维字符矩阵排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！