The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Miscellaneous

Problem :-
Given 2 strings, find all possible interleaved combination of the characters of the 2 strings.
Consider two strings " AB " & " PQ ".
Possible interleaved combination are :-
ABPQ | APBQ | APQB | PABQ | PAQB | PQAB

Solution :-
This problem is similar to the balanced parenthesis problem discussed earlier.
There are two possible options of interleaving characters of two strings.
1 ) First character of the interleaved string is from first string str1. We will recursively consider all the characters of str1 and str2 to obtain possible interleaved combinations.
2 ) First character of the interleaved string is from second string str2. We will follow the same recursive technique. See the implementation below.

#include<iostream>
using namespace std;

// print all possible interleaved combination of the characters of 2 strings
// start1 and start2 keeps track of the indices in str1[] & str2[] respectively
void printCombination(char str1[],char str2[],char str[],int size1,int size2,
int pos,int start1,int start2) { if(pos == size1+size2) { str[pos] = 0; // null terminate the string cout<<str<<endl; } if(start1 < size1) { str[pos] = str1[start1]; printCombination(str1,str2,str,size1,size2,pos+1,start1+1,start2); } if(start2 < size2) { str[pos] = str2[start2]; printCombination(str1,str2,str,size1,size2,pos+1,start1,start2+1); } } // wrapper function void interleave(char str1[],char str2[],int size1,int size2) { // character array to store the interleaved combination char str[size1*size2]; int pos = 0; // index of 'str' printCombination(str1,str2,str,size1,size2,pos,0,0); } // main int main() { char str1[] = {'A','B','P'}; char str2[] = {'C','D','Q'}; cout<<"\nPossible interleaved combination :-\n"; interleave(str1,str2,sizeof(str1),sizeof(str2)); cout<<endl; return 0; }

Back

All Miscellaneous Problems
* Print all possible permutation of array elements
* Given the number of parenthesis pairs, print all possible combination of Balanced Parenthesis
* Given a set with 'n' elements, print subsets of all possible sizes
* Given a triangle in the form of a lower diagonal matrix, find the weight of maximum path in the triangle
* Given a matrix of 0s & 1s, find the maximum size square submatrix with all values as 1
* Given a set with 'n' elements. Find the sum of maximum elements in all subsets of size 'p' such that p <= n
* Given 2 strings, find all possible interleaved combination of the characters of the 2 strings