WAP to Print Compbinations e.g combination of n things taken k at a time without or with repetitions

/*In mathematics a combination is a way of selecting several things out of a larger group, where (unlike permutations) order does not matter. In smaller cases it is possible to count the number of combinations. For example given three fruit, an apple, orange and pear say, there are three combinations of two that can be drawn from this set: an apple and a pear; an apple and an orange; or a pear and an orange. More formally a k-combination of a set S is a subset of k distinct elements of S. If the set has n elements the number of k-combinations is equal to the binomial coefficient

\binom nk = \frac{n(n-1)\ldots(n-k+1)}{k(k-1)\dots1},

which can be written using factorials as \frac{n!}{k!(n-k)!} whenever k\leq n, and which is zero when k > n. The set of all k-combinations of a set S is sometimes denoted by

\binom Sk\,.

Combinations can consider the combination of n things taken k at a time without or with repetitions.
*/

# include
using namespace std;
bool used[256]={0}; //Concept nCr
int r=3;
char a[] = "ABCD";
//int length=strlen(pIn);
void printOutPutArray(char *out,int outIndex){
for(int i=0;i cout<<"\n";
}

void combinations(char *out, int outIndex, int included,int length)
{
if (included==r) {printOutPutArray(out,outIndex); return;
}
for (int i=0;i{
if (used[i]) continue;
out[outIndex++] = a[i];
used[i]=1;
combinations(out, outIndex, included+1,length);
used[i]=0;
outIndex--;
}

}

//st above functions */
int main()
{
char out[100];
combinations(out, 0, 0,4);
return 0;
}

WAP to check reguler expression against text recursively

#include
using namespace std;
//check regexp against text recursively
bool match(char *regexp, char *text){
// the case regexp is empty, we don't need to check text == '\0'
if (*regexp == '\0') return (*text == '\0');
// the case ? and normal characters
if (*regexp == '?'||*regexp == *text) return match(regexp+1,text+1);
// the case *
if (*regexp=='*'){
do{
if (match(regexp+1,text)) return true;
}while (*text++!='\0');
}
return false;
}

int main(){
char p[4]={'a','*','d'};
char s[4] = {'a','c','b'};
bool k=match(p,s);
if(k) cout<<"yes";
else cout<<"no";
return 0;
}

A Product Array Puzzle

Given an array arr[] of n integers, construct a Product Array prod[] (of same size) such that prod[i] is equal to the product of all the elements of arr[] except arr[i]. Solve it without division operator and in O(n).

The above method can be optimized to work in space complexity O(1). Thanks to Dileep for suggesting the below solution.
?
void productArray(int arr[], int n)
{
int i, temp = 1;

/* Allocate memory for the product array */
int *prod = (int *)malloc(sizeof(int)*n);

/* Initialize the product array as 1 */
memset(prod,1,n);

/* In this loop, temp variable contains product of
elements on left side excluding arr[i] */
for(i=0; i {
prod[i] = temp;
temp *= arr[i];
}

/* Initialize temp to 1 for product on right side */
temp = 1;

/* In this loop, temp variable contains product of
elements on right side excluding arr[i] */
for(i= n-1; i>=0; i--)
{
prod[i] *= temp;
temp *= arr[i];
}

/* print the constructed prod array */
for (i=0; i printf("%d ", prod[i]);

return;
}

Time Complexity: O(n)
Space Complexity: O(n)
Auxiliary Space: O(1)


Optimization :

void ArrayMul(int buf[],int res[],size_t len) /*res[] is assumed to be of size len & all members initialized to 1 */
{
  size_t i;
  int left = 1,
		right = 1;

  for(i = 0; i<len;i++)
  {
	  res[i] *= left;
	  res[lenn-i-1] *= right;

	  left *= buf[i];
	  right *= buf[len-i-1];
  }
}

Given a matrix with elements only 0 and 1. Find the size of the largest submatrix containing all 1's. Also find the coordinates of the top left and bo

For example, consider the below binary matrix.

0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0

The maximum square sub-matrix with all set bits is

1 1 1
1 1 1
1 1 1

Algorithm:
Let the given binary matrix be M[R][C]. The idea of the algorithm is to construct an auxiliary size matrix S[][] in which each entry S[i][j] represents size of the square sub-matrix with all 1s including M[i][j] and M[i][j] is the rightmost and bottommost entry in sub-matrix.

1) Construct a sum matrix S[R][C] for the given M[R][C].
a) Copy first row and first columns as it is from M[][] to S[][]
b) For other entries, use following expressions to construct S[][]
If M[i][j] is 1 then
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
Else /*If M[i][j] is 0*/
S[i][j] = 0
2) Find the maximum entry in S[R][C]
3) Using the value and coordinates of maximum entry in S[i], print
sub-matrix of M[][]

For the given M[R][C] in above example, constructed S[R][C] would be:

0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 2 2 0
1 2 2 3 1
0 0 0 0 0

The value of maximum entry in above matrix is 3 and coordinates of the entry are (4, 3). Using the maximum value and its coordinates, we can find out the required sub-matrix.
?
#include
#define bool int
#define R 6
#define C 5

void printMaxSubSquare(bool M[R][C])
{
int i,j;
int S[R][C];
int max_of_s, max_i, max_j;

/* Set first column of S[][]*/
for(i = 0; i < R; i++)
S[i][0] = M[i][0];

/* Set first row of S[][]*/
for(j = 0; j < C; j++)
S[0][j] = M[0][j];

/* Construct other entries of S[][]*/
for(i = 1; i < R; i++)
{
for(j = 1; j < C; j++)
{
if(M[i][j] == 1)
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1;
else
S[i][j] = 0;
}
}

/* Find the maximum entry, and indexes of maximum entry
in S[][] */
max_of_s = S[0][0]; max_i = 0; max_j = 0;
for(i = 0; i < R; i++)
{
for(j = 0; j < C; j++)
{
if(max_of_s < S[i][j])
{
max_of_s = S[i][j];
max_i = i;
max_j = j;
}
}
}

printf("\n Maximum size sub-matrix is: \n");
for(i = max_i; i > max_i - max_of_s; i--)
{
for(j = max_j; j > max_j - max_of_s; j--)
{
printf("%d ", M[i][j]);
}
printf("\n");
}
}

/* UTILITY FUNCTIONS */
/* Function to get minimum of three values */
int min(int a, int b, int c)
{
int m = a;
if (m > b)
m = b;
if (m > c)
m = c;
return m;
}

/* Driver function to test above functions */
int main()
{
bool M[R][C] = {{0, 1, 1, 0, 1},
{1, 1, 0, 1, 0},
{0, 1, 1, 1, 0},
{1, 1, 1, 1, 0},
{1, 1, 1, 1, 1},
{0, 0, 0, 0, 0}};

printMaxSubSquare(M);
getchar();
}

Time Complexity: O(m*n) where m is number of rows and n is number of columns in the given matrix.
Auxiliary Space: O(m*n) where m is number of rows and n is number of columns in the given matrix.
Algorithmic Paradigm: Dynamic Programming

Write a function which will accept a Binary Search Tree and convert it to a sorted Doubly linked Lis

struct Node{
int data;
struct Node *left;
struct Node *right;

}
I have named the two pointers as left and right, but they can be named pre/next or anything.

If we are codding in C++, then we can take the advantage of Object Oriented Programming and define the Node as a Class, The benefit we will get is that we can also define the constructor and/or other operations, like below, I have also defined a constructor which initializes the pointers to NULL in the member initialization list of constructor


#include
#include
using namespace std;


struct node
{
int data;
struct node* left;
struct node* right;

};

//typedef struct node Node;

/** Helper function to create a sample tree. Used to debug the program.
* It create the below tree and returns a pointer to the root.
*
* 4
* / \
* 2 5
* / \
* 1 3
*/
/** Prints the in Inorder Tracersal of the tree pointed to by r.
*/
void printInorder(struct node* r)
{
if(!r){ return; }

printInorder(r->left);
cout<<" "<data;
printInorder(r->right);
}

/** Prints the Doubly link list whose head is at h linearly.
*/
void printDoublyList(struct node* h)
{

while(h)
{
cout<<" "<data;
h = h->right;
}
cout<data;

}

struct node* append(struct node *a,struct node *b)
{
if(a==NULL)return b;
if(b==NULL)return a;

//struct node* result=a;

a->right=b;
b->left=a;

return a;

}

/** Recursively convert a Binary Tree to a Doubly Linked List
*/
struct node* treeToList(struct node* r)
{

// Terminating Condition of Recursion
if (r == NULL){ return NULL; }

// Convert to list the left and right subtrees recursively
struct node *prev = treeToList(r->left);
struct node *next = treeToList(r->right);

// Making the root Node a separate list
r->left = NULL;
r->right = NULL;

/* Append everything together in sorted order */
prev = append(prev, r);
prev = append(prev, next);

return(prev);
}

struct node* Node(int data)
{
struct node *temp=(struct node *)(malloc(sizeof(struct node)));
temp->data=data;
temp->left=NULL;
temp->right=NULL;

return temp;
}

int main()
{
struct node *r = NULL;
r = Node(4);
r->left =Node(2);
r->left->left = Node(1);
r->left->right = Node(3);
r->right = Node(5);
r->right->left = Node(6);
r->right->right = Node(7);



cout<<"In order Tracersal :";
printInorder(r);

r = treeToList(r);
cout<<"\nList :";
printDoublyList(r);

getchar();
return 0;
}
Run Here https://ideone.com/SVhKd
Run here https://ideone.com/clone/vMBw1

Permutation of String

Hey guys..I know Most of You Stuck with this Question...here i am posting a excellent so0lution fro problem hope this will help you ..lot..
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.
Explanation
Let’s assume a given string S represented by the letters A1, A2, A3, ..., An
To permute set S, we can select the first character, A1, permute the remainder of the string to get a new list. Then, with that new list, we can “push” A1 into each possible position.
For example, if our string is “abc”, we would do the following:
1. Let first = “a” and let remainder = “bc”
2. Let list = permute(bc) = {“bc”, “cd”}
3. Push “a” into each location of “bc” (--> “abc”, “bac”, “bca”) and “cb” (--> “acb”, “cab”, “cba”)
4. Return our new list

?

import java.util.*; class Permutation { public static ArrayList getPerms(String s) { ArrayList permutations = new ArrayList(); if (s == null) { // error case return null; } else if (s.length() == 0) { // base case permutations.add(""); return permutations; } char first = s.charAt(0); // get the first character String remainder = s.substring(1); // remove the first character ArrayList words = getPerms(remainder); for (String word : words) { for (int j = 0; j <= word.length(); j++) { permutations.add(insertCharAt(word, first, j)); } } return permutations; } public static String insertCharAt(String word, char c, int i) { String start = word.substring(0, i); String end = word.substring(i); System.out.println("start=" + start + "\t c=" + c + "\t end=" + end ); return start + c + end; } public static void main(String a[]) { ArrayList perm = new ArrayList(); perm=getPerms("abc"); //for(String ele:perm) //System.out.println(ele); } }

Compile: javac Permutation.java
Run: java Permutation
/*output analysis
start= c=c end=
start= c=b end=c
start=c c=b end=
start= c=a end=bc
start=b c=a end=c
start=bc c=a end=
start= c=a end=cb
start=c c=a end=b
start=cb c=a end=
*/



2nd Method

# include
# include

int printPermutations(char *str,int size, int pos)
{
int i;
int total=0;

if(pos==(size-1))
{
puts(str);
return 1;
}

total+=printPermutations(str,size,pos+1);
for(i=pos+1;i
{
int j;
for(j=pos;j
if(*(str+j)==*(str+i))
break;

if(j==i)
{
char tmp=*(str+pos);
*(str+pos)=*(str+i);
*(str+i)=tmp;

total+=printPermutations(str,size,pos+1);

tmp=*(str+pos);
*(str+pos)=*(str+i);
*(str+i)=tmp;
}
}

return total;
}

int main()
{
char str[]="aabc";
int size,total;



size=strlen(str);

printf("\n\nAll permutations of the input string are:\n");
total=printPermutations(str,size,0);

printf("\n\nThe total number of permutations of the given string is %d",total);


return 0;
}

Run here https://ideone.com/iXkV6

String Permutation Using  Iterative Appropach https://tropenhitze.wordpress.com/2010/01/25/steinhaus-johnson-trotter-permutation-algorithm-explained-and-implemented-in-java/

Anagram Cracker

Two words are anagrams if and only if they contain the exact same letters with the exact same frequency (for example, "name" and "mean" are anagrams, but "red" and "deer" are not).

Given two strings S1 and S2, which each only contain the lowercase letters a through z, write a program to determine if S1 and S2 are anagrams. The program must have a running time of O(n + m), where n and m are the lengths of S1 and S2, respectively, and it must have O(1) (constant) space usage.

Find Minimum Number of Jumps Requred to Jump From Start to Last Position in an Unsorted Array .Array May Contain The Value 0s & Duplicates as Well (Spacial Case)

You Might Hate me because of Formatting :) Will Update it Asap :)

You are given an array of positive integers. You have to traverse the array with rules that if you are on ith element u can make max arr[i] jumps i.e. if you are at element with value zero you cannot move forward. Find the least number of jumps required to reach the end of the array.
ex: 1 3 5 8 9 2 6 7 6 8 9 .....

This array requires 3 jumps Suggest the algo to find minimum number of jumps.... 1 to 3 to 9 to last 9 ( we want optimal solution )

Greedy Approach(Doesn't Gives Optimal Solution)

Algorithm:
We Know that from ith location we can jump only maximum a[i] , so greedly we will keep goin & icrementing the jump untill we won't reach end of the array.
so in loop i=0 to size of array we will iterate through a[i] & w3ill check if a[i+j]+j ie greater then max or not if its true then we will update the max & repat the same logic. this we will reach to end of the array but doesn't gurantee that it will be optimal. e.g. fro above case it will return 3 jumps but for this case 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9,1,1,1 which requires minimum number of jumps is 3 but this algo will produce jump 4.

Here is Naive but not Optimal Solution

#include
int main()
{
int arr[]={1, 3, 5 ,8 ,9 ,2 ,6, 7, 6, 8, 9};
int size=sizeof(arr)/sizeof(int);

int i=0,jump=0,step,max,j;

while( i< size) { jump++; max=0; step=0; /*computes max distance it can cover in this jump*/ for(j=1;j<=arr[i];j++) { if(arr[i+j]+j>max)
{
max=arr[i+j]+j;
step=j;
}
}
i=i+step;
}

printf("%d ",jump);

}

Time Complexity O(N^2)
Space Compelxity O(1)
Run Here https://ideone.com/ZBQN8 Correct Test Case
Run Here https://ideone.com/apTHY Failed Test Case



2nd Solution Using Dynamic Programming Simple & More Efficient
As We Know Dp can solved using Bottom-Up and Top-Down Appraoch
This Algorithm is Designed By My Friend Sambsiva

Algorithm (Bottom Up Approach but Memozation)

According to Him Lets define a function called hop which is number of steps required to reach the end of array from the given position, So

hop(i) = INT_MAX if a[i] == 0 e.gh. if value is zero at ith position we can't jump

hop(i) = 1 + min(hop(j) where j is from i + 1 to i + a[i]

hop(0) is the required answer

i.e.

#include
#include
int minhops(int a[], int n)
{
int hop[n] ; int i = n;
while(i--)
{
if(a[i] == 0)
hop[i] = INT_MAX;

else
{
if(i + a[i] >= n)
hop[i] = 1;
else
{
int j, min = INT_MAX;
for(j = i + a[i]; j > i; --j)
{

if(hop[j] < min) min = hop[j]; } hop[i] = min + 1; } } } return hop[0];

}

int main() {
 
    int a[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9,1,1,1};
  //{1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};//{1, 3, 6, 0, 0, 3, 2, 3, 6, 8, 9};
    int n = minhops(a, 14);
 
    if(n != INT_MAX)
        printf("%d\n", minhops(a, 14));
 
 
    return 0;
}
 
 

 Complexity Analysis Since we are running 2 loops here and iterating from 0 to I in every loop then total time takes will be 1 + 2 + 3 + 4 + … + (N-1). So time efficiency O(n) = O(n*(n-1)/2) = O(n^2) Time Complexity O(N^2) Space Complexity O(N) Run Here https://ideone.com/v4Go4 Algorithm

(Top-Down Approach-Memoization)

Step 1. Declare an array of size N say jump[N];
where ith position indicates the number of jumps requires to reach from start to this (ith) position in array .

Step 2. Initialize jump[0]=0; indicates to reach oth location form starting location (3which is obviuosly 0) we don't requires any jump.

Step 3. Check size of array and value at 0th location in array For first index, optimum number of jumps will be zero. Please note that if value at first index is zero, we can’t jump to any element and return infinite.so these tow cases are
                  A.If size of array==0 means array is of zero size;
                 B.If value at zero then we can't jump or we can't proceed to next location Step 4. Run Through Loop for remaining elements in array and Initialize jump[i] as infinite. where 
           1<=i<=N.
           Sub-step 4A. (Please Note j runs in inner loop until i<=j+a[j] )
            if jump[i]<jump[j]+1 update jump[i] & repeat until j>i (this whole processing will happen in
            inner loop). e.g. for each ith element this loop will run & tries to figure out optimal/minimum
           number of jumps required to reach this ith position from starting of array .

Step 5. After running above algorithm we will return array[n-1] that will show number of jumps required
to reach last elemnt in array from start.

#include<stdio.h>

#include<limits.h>

int MAX=INT_MAX-1;
unsigned int minJump(int a[], int n)
{
unsigned int *jump= new unsigned int[n];
int i, j;

/*Boundary Cases
1.If n==0 means array is of zero size;
2.If value at zero then we can't jump or we can't proceed to next location
*/

if (n == 0 || a[0] == 0)
return MAX;

jump[0] = 0; //no need to jump at first element

for (i = 1; i < n; i++)
{
jump[i] = MAX; //Initialization of jump[i]

for (j = 0; j < i; j++)
{
//check if jump is possible from j's to ith location where j <=i
if (i<=j+a[j])//because from jth location we can jump up to j+a[j] only
{
//check if better solution available
if ((jump[j] + 1) < jump[i])
jump[i] = jump[j] + 1; //updating jump[i] to optimal jumps
}
}
}

return jump[n-1];

}

int main()
{
int arr[]={1, 3, 6, 0, 0, 3, 2, 3, 6, 8, 9}; ;//{1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9,1,1,1};//{1, 3, 6, 0, 0, 3, 2, 3, 6, 8, 9};

int size=sizeof(arr)/sizeof(int);

printf("%d ",minJump(arr,size));

}
Complexity Analysis
Since we are running 2 loops here and iterating from 0 to I in every loop then total time takes will be 1 + 2 + 3 + 4 + … + (N-1).
So time efficiency O(n) = O(n*(n-1)/2) = O(n^2)

We also need O(n) space for jump array.

Time Complexity O(N^2)
Space Complexity O(N)
Run Here https://ideone.com/NIC1x , https://ideone.com/BwAjg