4x4 2D matrix permutations

Question

I have a 4x4 two-dimensional array, for example:

ABCD UALE TSUG NEYI 

Now I will need to find all permutations of 3 characters, 4 characters, etc. to 10.

So, some of the words you can “find” from this are TEN , BALD , BLUE , GUYS .

I was looking for SO for this and Googled, but no specific help. Can you push me in the right direction, in what algorithm should I study (maybe?)? Please be careful, because I am not a guy with algorithms (not all of us (well, at least the majority :)), but I want to know, I don’t know where to start.

Answer 1

Ahhh, that the Boggle game is not ... You do not want permutations, you need a graph, and you want to find words on a graph.

Well, I would start by placing the characters in the form of graph nodes and connecting them with their nearest and diagonal neighbors.

Now you just want to find a schedule. For each of the 16 starting nodes, you are going to perform a recursion. When you switch to a new node, you must indicate it as used so that you cannot go to it again. When you leave the node (having searched it completely), you untie it.

I hope you see where this is happening ...

For each node, you will visit each of its neighbors and add this symbol to the string. If you created your dictionary based on this search, you can immediately find out if the characters that you still have are the beginning of the word. This greatly complicates the search.

Some kind of dictionary I'm talking about is where you have a tree, the nodes of which have one child for each letter of the alphabet. The beauty is that you only need to save the node tree that you are currently using in the search. If you decide you have found a word, you simply go back through the parent nodes to determine which word it is.

Using this tree style along with finding the depth graph, you can simultaneously search for ALL possible word lengths. This is the most effective way that I can think of.

---

Let me just write a pseudocode 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, drop all of this:

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

It remains only to build a graph and a dictionary. And I just remembered the name of this dictionary data structure! This is Trie . If you need more storage space, you can compress in Radix Tree or the like, but by far the easiest (and fastest) is to simply use the direct Trie.

Answer 2

Since you do not define the preferred language that I implemented in 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; } 

Code to get the results:

  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); 

Change parameter 3 to the desired text length.

Answer 3

It seems you are just using a 4x4 matrix as an array of length 16. If so, you can try a recursive approach to generate permutations up to length k as follows:

 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) 

The idea is to print each “candidate” that has more characters, then downLim (3 in your case) and ends when you reach the high limit ( highLim ) - 10 in your case.

At each point in time, you “guess” which character is next, and then add it to the candidate and call it recursively to find the next candidate.
Repeat the process for all possible guesses.

Please note that there is a choice of (10.16) * 10! + select (9.16) * 9! + ... + select (3.16) * 3! different such permutations, so it may take a long time ...

---

If you need meaningful words, you will need some kind of dictionary (or statistically extract it from some context) to match candidates with “real words”.