Need help with this recursive problem (JavaScript)

[Jamin2112]

Okay, so I have a function single_ops(w) that returns a JavaScript array of all strings that can be made from 1 operation on the string w:

		function single_ops(w)
		{
			/* Given a word w, return an array of all strings that are w with:
			
			   (1) 1 letter inserted, that letter being one which is distance
				   1 away on the keyboard
			   (2) 1 letter replaced, that letter being one which is distance
				   1 away on the keyboard
			   (3) 1 letter removed
			   (4) 2 adjacent letters swapped
			*/
			var A = new Array(); // Associative array to store words, so we can add them w/out addding repeats
			for (var i = 0, j = w.length; i < j; ++i)
			{
				var closeChars = kdmap[w[i]];
				var s1a = w.slice(0,i); // equals w[0], ..., w[i-1]    
				var s2a = w.slice(i,j); // equals w[i], ..., w[j-1]    
				var s1b = w.slice(0,i+1); // equals w[0], ..., w[i]
				var s2b = w.slice(i+1,j) // equals w[i+1], ..., w[j-1]
				for (var k = 0, n = closeChars.length; k < n; ++k)
				{
				    var cc = closeChars[k];
					// (1) ----------------------------------------------
					A[s1a + cc + s2a] = 1; // equals w[0],..., w[i-1], cc, w[i],..., w[j-1]
					A[s1b + cc + s2b] = 1; // equals w[0], ..., w[i], cc, w[i+1], ..., w[j-1]
					// (2) ----------------------------------------------
					A[s1a + cc + s2b] = 1; // equals w[0], ..., w[i-1], cc, w[i+1], ..., w[j-1]
				}
				// (3) --------------------------------------------------
				if (j > 1)
				    A[s1a + s2b] = 1; // equals w[0], ..., w[i-1], w[i+1], ..., w[j-1]
				// (4) --------------------------------------------------
				A[s1a + s2b.slice(0,1) + s2a.slice(0,1) + s2b.slice(1,s2b.length)] = 1;
			}
			return A;
		}

Yes, I know the procedure is messy and crappy. But it works for now. My problem is something different.

I want a procedure that uses that recursively calls that function so that I can have a set of all strings made from n operations on w. In other words, call the function once, returning an array A of all strings that are formed from 1 operation on w then, on each element of A, call the function again and merge the elements of the returned array to A, etc.

I'm working on it but having trouble with the part where I have a variable that is limiting the number of recursions. Any help?

 

[.Scott]

You don't really need recursion for this, just a loop that run "n" times.
Of course, when n gets to be more than 2, you're going to be consuming significant processor and memory resources.

Also, you seem to be mixing characters in a string with characters in an array.

Suggest you change:
var closeChars = kdmap[w];
to
var closeChars = kdmap[w.charAt(i)];

I will post a solution in a moment.

 

[.Scott]

Here you go:

var distance = 2;
var neighbors = Array();
var allneighbors = Array();
allneighbors["was"] = 1;
neighbors["was"] = 1;//
for(i=0;i<distance;i++) {
  newneighbors = new Array();
  for (newword in neighbors) {
    var wordneighbors = single_ops(newword);
    for (word in wordneighbors) {
      if(allneighbors[word]!=1) {
        allneighbors[word] = 1;
        newneighbors[word] = 1;
      }
    }
  }
  neighbors = newneighbors;
}

for (word in allneighbors) {
  document.write("<br>"+word);
}

 

[Jamin2112]

You don't really need recursion for this, just a loop that run "n" times.
Of course, when n gets to be more than 2, you're going to be consuming significant processor and memory resources.

I have constructed my algorithm so that n is proportional to the length of the word, so that longer words are expected to have more room for error. I have n=w.length/8+1, but I might even change it to n=w.length/10+1. It's expected that the user will be using gigantic words rarely.

Also, you seem to be mixing characters in a string with characters in an array.

Suggest you change:
var closeChars = kdmap[w];
to
var closeChars = kdmap[w.charAt(i)];

I thought those were equivalent?

 

[DavidSnider]

I have constructed my algorithm so that n is proportional to the length of the word, so that longer words are expected to have more room for error. I have n=w.length/8+1, but I might even change it to n=w.length/10+1. It's expected that the user will be using gigantic words rarely.
I thought those were equivalent?

Using the array method has some compatibility issues with older browsers. It is faster though.

 

[.Scott]

I have constructed my algorithm so that n is proportional to the length of the word, so that longer words are expected to have more room for error. I have n=w.length/8+1, but I might even change it to n=w.length/10+1. It's expected that the user will be using gigantic words rarely.

Of course it will be the largest words that will give you the biggest problems. A really long word will bring your computer to a halt as surely as pneumonultramicroscopicsilicovolcanokoniosis.

Also, you seem to be mixing characters in a string with characters in an array.

Suggest you change:
var closeChars = kdmap[w];
to
var closeChars = kdmap[w.charAt(i)];

I thought those were equivalent?

It didn't work on my Firefox at work. As I recall, it's a version that's about 2 years old.
In any case, I hope your code is working smoothly.

 

[FactChecker]

Is this what the OP was asking for?

Make a recursive program that receives n as a parameter. When the incoming parameter n > 1, make recursive calls passing n-1 down. When the incoming parameter n=1, just execute your existing program and return.

 

[.Scott]

[STRIKE]It didn't work on my Firefox at work.[/STRIKE]

Correction, I tried it with Explorer 9 (2011) at work. That's were it didn't work.

 

[.Scott]

Is this what the OP was asking for?

Make a recursive program that receives n as a parameter. When the incoming parameter n > 1, make recursive calls passing n-1 down. When the incoming parameter n=1, just execute your existing program and return.

You would also need to consolidate the list of results.
Also the program as I implemented it, checks for words that have already been checked - so that you don't end up rechecking the same words over and over.
He asked for a recursive process, but I believe he was looking for a practical solution. The algorithm I presented was recursive - but it did not use recursive function calls.

 

[FactChecker]

He asked for a recursive process, but I believe he was looking for a practical solution. The algorithm I presented was recursive - but it did not use recursive function calls.

Ok. The last line of the OP asked a fundamental question about how to design a recursive solution and I thought it would not hurt to answer it. And of course you are right that there are other details to deal with.

 

[harborsparrow]

Using recursion in Javascript may not be very easy. Javascript allows its functions to be called from anywhere, in such a way that the function context (surrounding environment) can be passed into the procedure as a parameter. Many programmers use Javascript for years without becoming aware of this capability. So you can have procedures inside procedures, and when you call the inner procedure (from anywhere!) it has the context of the surrounding procedure.

In other words, Javascript allows "closures" (in a computer science sense of the word).

Given that the average programmer finds it somewhat difficult to understand how to implement recursion anyway, this is a double hazard. In recursion, you have to make sure every variable used as part of the recursion is a local variable (declared within the recurring function) so that each invocation of the function adds new copies of those variables to the call stack. And then, you have to check first (within the function) for the case that ends the recursion.

I've never tried doing recursion in Javascript, and I seldom do it at all because of the performance hit of growing the stack during recursion. Since javascript has closures, it does not manage the call stack in the same way that C or C++ does. Thus, I think it might be risky to attempt recursion in Javascript. More risky than usual.

That said, here's a link claiming to do recursion in Javascript. I have not tested it: http://www.htmlgoodies.com/primers/jsp/article.php/3622321