C Code for Longest Common Subsequence Using Recursion

Here's the C Code for Longest Common Subsequence Using Recursion :-



Output :-

Length of LCS is 5

Continue Reading →

Insertion Sort using Binary Search in Python

English: an example on insertion sort (Photo credit: Wikipedia)

Sorting is a very essential concept in programming and Computer Science. There are different types of sorting algorithms available. Today in this post I will share a code which demonstrates Insertion sort. But unlike the default linear search being used in the algorithm I have used binary search to perform the searching. The following code gives the little example of Insertion Sort using Binary Search. The code has been written in Python.

Linear search takes O(n) to search for an element where as binary search takes O(log n) number of comparisons to search an element. Asymptotically Binary Insertion Sort is no better than linear insertion sort in worst case scenario. But the the latter has few comparisons of Order O(nlog n)

In best case Linear insertion sort is better since it will take O(n) comparisons where as binary insertion sort takes O(nlog n)

Here's the code :-

Continue Reading →

String Permutations Algorithm with example code in C/C++

Permutations of 3 balls (Photo credit: Wikipedia)

Hello Everyone,

Today I will be telling you how to print all the possible permutations of a string provided by the user. I will show you the recursive way to do this. The programming paradigm that we use in case of Recursion is backtracking.

What do you mean by Permutations ?

A permutation, also called an “arrangement number” or “order,” is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself. A string of length n has n! permutation.

For more info visit here --> http://mathworld.wolfram.com/Permutation.html

Recursion

This is a bad method for printing permutations since its time complex i.e. it takes more time to execute than the iterative method this is because of the extensive use of the call stack. Now the following image explains the recursion technique. The image presents the recursion tree of the method of permutations generation. We take the example string that we permute as "GOD".

In order to find all possible combinations for a given string, then start at a position i, then find and place all possible letters in position i. Every time we put a new letter in position i, we should then find all the possible combinations at position i+1 – this would be the recursive call that we make.

Here's the C++ implementation string permutation.

Now the above code will print all the permutations of the string "GOD" without repetition. But if you want to print them lexicographic manner i.e where the repetitions of the characters are included then read the matter below.

Since we are going in lexicographic order, so we have to do the following ,its pretty much understandable. (Note : the numbers represent index and 1 means the starting index , we will not use 0 for the first index as we do it in programming.)

• Start with index '1' and then recurse over rest of the 'n - 1' numbers.
                 
  • Start with '2' and then recurse over rest of the 'n - 2' numbers.
  • Start with '3' and then recurse over rest of the 'n - 2' numbers.
    :
    :
  • Start with 'i' and then recurse over rest of the 'n - 2' numbers.
    :
    :
  • Start with 'n' and then recurse over rest of the 'n - 2' numbers.
    
• Start with a '2' and then recurse over rest of the 'n - 1' numbers.
  
  
  • Start with '1' and then recurse over rest of the 'n - 2' numbers.
  • Start with '3' and then recurse over rest of the 'n - 2' numbers.
    :
    :
  • Start with 'i' and then recurse over rest of the 'n - 2' numbers.
    :
    :
  • Start with 'n' and then recurse over rest of the 'n - 2' numbers.
    
• :
  :
• Start with 'i' and then recurse over rest of the 'n - 1' numbers.
  :
  :
• Start with 'n' and then recurse over rest of the 'n - 1' numbers.

Important thing to note is, in every recursion you start with the minimum numbers left, to be printed, and then keep picking the next minimum, and so on, till you exhaust all the 'n' numbers.

Here's the C Code for Lexicographical Permutations.

Related articles

• How To copy a Very large file to a flash drive in Linux
• 3D Rotating Square with WebGL in Three.js
• Example of Path class in Java NIO
• Don't Call Yourself A Programmer
• The Hackers Manifesto - Conscience of a Hacker
• Java Code to implement a Stack using Java Generics

Continue Reading →