Time: 2300 hours IST
Location: Imaginary
 

“Will you cut that out?” screamed Stack. “I’m going to overflow here.”

(Meet Stack. He is the one who stores information about the active subroutines of a computer program and carries a huge burden of data on his shoulders, while strictly conforming to the last-in-first-out principle. There are many similar stacks for other programs in Memory.)

“Hey! There ain’t nothing I can do about it. Compiler gave me some code and I’m executing it,” replied Interpreter.

(Say Hello to Interpreter. She executes stored precompiled code created by her brother, Compiler)

“Listen up, Compiler! If you don’t do something fast, I will overflow!” screamed Stack.

“So?? What can I do?” answered Compiler, rudely. “Don’t look at me. It ain’t my fault. It’s that idiotic programmer, Jack’s fault. His program contains a method that keeps calling itself. He must have forgotten to type out a base case for termination. I don’t have the ability to warn him about that….”

(Say Hello to Compiler. He transforms source code written into bytecode that can be interpreted by his sister.)

“Ok. That’s it! I can’t take it anymore. Whoever’s responsible, catch this!” and Stack stopped accepting any more data. Instead, Stack threw an error. The programmer, who was the creator of that buggy program, saw the following message on his monitor:

“Phew! That was close! After throwing up, I’m relieved! I’m feeling much better now,” said Stack, looking around, expecting to see everyone smiling. Instead, he could perceive only depressed beings.

“What’s with the gloomy faces?” asked Stack.

Compiler looked at Stack and replied, “Let’s just hope that that idiot of a programmer spots that bug before he runs that program again. It’s really stressful in here.”

“By the way, what exactly is that programmer trying to accomplish?” asked Interpreter, who had suddenly woken up from her reverie.

“I have no clue, but Editor might know. Hey Editor!” shouted out Compiler. “Can ya spare a few moments?”

Editor turned around and shouted back, “I’m kinda busy here. What d’ya want?”

(Say Hello to Editor, who is, in fact, a source code editor designed specifically for editing source code of computer programs by programmers. He is extremely proud of his syntax highlighting, autocomplete and bracket matching functionalities.)

“We just wanted to know the nature of the program that idiot is trying to code.”

“Wait…Let me check my buffers. Aha! Here’s something that might help. There’s a function called permute and it contains the following code:

private static void permute(String str)
{
	permute("", str);
}

private static void permute(String prefix, String rest)
{
	if(rest.length() == 0)
		System.out.println(prefix);
	else
	{
		for(int i=0; i<rest.length(); i++)
		{
			String newPrefix = prefix + rest.charAt(i);
			String newRest = rest.substring(0, i) + rest.substring(i+1);
			permute(newPrefix, rest);
		}
	}
}

“Hope this helps!” shouted Editor, and without waiting for any acknowledgement, turned back and resumed his work.

“Wish we were intelligent enough to figure out what this piece of code does,” said Interpreter.

“That programmer didn’t forget to write the base case. So, there ain’t no problem with that. Must be some logical error! I hate logica…” Before Compiler could complete, he received an instruction to begin compiling. “Ok. Time to get to work! Here it comes again. Let’s just hope the bug has been removed!” and the whole process began again.

However, a few microseconds later, the same StackOverflowError message appeared. This process was repeated four more times, until VLC Player suddenly woke up from his slumber.

(Say hello to VLC Player. He is a highly portable free and open-source media player and supports many audio and video compression methods and file formats.)

“Hey, people! You can relax for awhile. Jack is taking a break and listening to some music!” exclaimed VLC.

“Oh…That’s wonderful. We all need rest. Perhaps Jack will find the bug after the break,” guessed Stack.

And all the other processes shouted out “Thank you, VLC!” together and fell asleep…well, almost.

________________________________________________________________________

Out of the blue, all the sleeping processes were awakened by a young, energetic voice saying, “Sorry to wake you up, guys, but I just had to…I couldn’t help overhearing your little conversation.”

“Well, what about it, Firefox?” asked Interpreter, partly annoyed.

(Say hello to Firefox, the youngest member of the gang. She is a web browser responsible for retrieving, presenting, and traversing information resources on the World Wide Web.)

“When I heard you mention the word “permute”, I recalled that Jack had been searching for information about that earlier today. I checked my cache to confirm, and apparently, he’s been reading a lot about recursive functions to compute permutations.”

“Well, that explains why there’s a method that keeps on calling itself,” added Compiler, as though he knew it all along.

“Did he manage to find a program for that?” asked Stack.

“Apparently, no! There isn’t any source code in my cache. I would have searched online myself, if I was allowed to. But thanks to Antivirus there, I won’t be able to do so,” explained Firefox, pointing to a stiff figure far away, “We wouldn’t even have to look at him if we all lived in Ubuntu. But here we are. In Windows. The only good point is he allows us to talk amongst ourselves.”

All the other processes turned to look at Antivirus, who never spoke to them, but always took any opportunity to pounce on anyone who exhibited suspicious behavior. True, he did a good job catching viruses 80% of the time, but he seemed too paranoid to everyone except himself.

“Anyway,” continued Firefox. “I do possess in my cache, a document containing an algorithm that Jack might be using. Here it is,” and she displayed the following:

If you are limited to iterative control structures, finding a general solution that works for strings of any length is difficult. Thinking about the problem recursively, on the other hand, leads to a relatively straightforward solution.The key to solving the permutation problem recursively is recognizing that the permutations of the (for instance) four-character string “ABCD” consist of the following strings:

  • The character ‘A’ followed by every possible permutation of “BCD”
  • The character ‘B’ followed by every possible permutation of “ACD”
  • The character ‘C’ followed by every possible permutation of “ABD”
  • The character ‘D’ followed by every possible permutation of “ABC”
void permute(string str)
{
     permute("", str);
}

The Recursive Permute procedure follows the outline of the recursive permutation

algorithm and has the following pseudocode form:

void permute(string prefix, string rest)
{
   if (rest is empty)
   {
      Display the prefix string.
   }
   else
   {
      For each character in rest
      {
         Add the character to the end of prefix.
         Remove character from rest.
         Use recursion to generate permutations with the updated values for prefix and rest.
      }
   }
}

The prefix starts empty and all the original letters still remain to be examined, which gives you the original problem. As the prefix grows and there are fewer characters remaining, the problem becomes simpler. When there are no characters remaining to be permuted, all characters have been placed in the prefix, and it can be displayed exactly as it appears.

The following video demonstrates how permutations are generated using recursion. Seems magical at first, but then, you’ll find it’s extremely logical. Watch it once, twice or how many ever times you like until you understand. It’s important!

Go ahead. Try it out!

After reading the entire document, Compiler commented, “Wow! Recursion seems to be magical. I wonder what all can be accomplished with recursion.”

Stack, who was more skeptical, said, “If it’s so good, then why ain’t it working? I don’t believe it. Why is it making me overflow?”

“Let’s find out by comparing the algorithm and code together,” suggested Firefox. And so, they did.

void permute(string prefix, string rest)
{
if (rest is empty)
{
Display the prefix string.
}
else
{
For each character in rest
{
   Add the character to the end of prefix.
   Remove character from rest.
   Use recursion to generate permutations with the updated values for prefix and rest.
}
}
}
static void permute(String prefix, String rest)
{
	if(rest.length() == 0)
    {
		System.out.println(prefix);
    }
	else
	{
		for(int i=0; i<rest.length(); i++)
		{
			String newPrefix = prefix + rest.charAt(i);
			String newRest = rest.substring(0, i) + rest.substring(i+1);
			permute(newPrefix, rest);
		}
	}
}

After a few microseconds had passed, Interpreter shouted out, “I’ve found it!”

“Where’s the bug?” asked Stack.

“If you observe the 13th line carefully (Is that unlucky or what?), the algorithm says, ‘Use recursion to generate permutations with the updated values for prefix and rest’…Notice the word, updated…Now, look at the last line of the source code which says, ‘permute(newPrefix, rest)’ and…” Interpreter was interrupted.

“…and instead of newRest, which is the updated version of rest, the unmodified version of rest is passed as the second argument!” continued Firefox after the light dawned on her.

“Precisely! That’s why control never reaches the base case because rest.length() never ever returns zero.”

“That was an awesome discovery, Interpreter…Too bad we still have to hope that Jack discovers this bug himself,” said Stack in a disappointed tone.

“Not necessarily,” declared Editor, who had been listening passively. “I can aid Jack in discovering the bug.” Saying that, Editor immediately constructed a red-line underneath the words ‘permute(newPrefix, rest)’. At the same time, VLC informed them that Jack had finished listening to music and was resuming his work.

Jack had fallen asleep while listening to music and had had some weird dreams. However, after this break, he was feeling somewhat refreshed, albeit a little drowsy. When Jack maximized the editor window, he noticed something that hadn’t caught his attention earlier. He spotted the underlined words, and after wondering how that had come into existence, his eye caught sight of the parameter ‘rest’. Then it hit him. He immediately placed his hands on the keyboard and inserted ‘new’ as a prefix to rest. He ran the program to generate all permutations of the string “abc” and the following output appeared:

Satisfied that he had finally accomplished what he had set out to do, Jack shut down his computer and prepared to go to sleep considering that it was almost midnight. At the moment when he was just about to fall asleep, he wondered how that red line had appeared out of the blue. He whispered to himself, “I must get some sleep. I’m imagining all sorts of things…”

The END

Note: The program and algorithm discussed in this story were obtained from the book: Programming Abstractions in C++ – Eric S. Roberts and Julie Zelenski

Comments
  1. Ravikiran kalal says:

    nicely presented Mr.Anderson. . .As always. . .:)

  2. Jinkchak says:

    @Anonymous and @sachin: Thank you! 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s