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 :-
Print all possible permutation of array elements.
Consider the array { 3, 2, 5 }.
Possible permutations : { 3, 2, 5 } | { 3, 5, 2 } | { 2, 3, 5 } | { 2, 5, 3 } | { 5, 2, 3 } | { 5, 3, 2 }

Solution :-
An array of length n has n ! permutations.
The implementation show below uses a recursive approach with swapping of array elements to obtain possible permutations and then swapping of elements in the permuted arrays to obtain further permutations.
We iterate over the array elements and at each iteration level, we do the swap and permute step described above. After the jth iteration, j elements in the obtained permuted arrays are fixed and we move to the next iteration.

#include<iostream>
using namespace std;

// swap elements in the array
void swap(int arr[],int idx1,int idx2) {
   int temp;
   temp = arr[idx1];
   arr[idx1] = arr[idx2];
   arr[idx2] = temp;
}

// print the permutation
void printPermute(int arr[],int size) {
   int i;
   for (i=0;i<=size;i++) {
      cout<<arr[i]<<" ";
   }
   cout<<endl;
}

// permute the elements recursively
void permute(int arr[],int start_idx,int end_idx) {
   int i;
   if (start_idx == end_idx) {
      printPermute(arr,end_idx);
   }
   for (i=start_idx;i<=end_idx;i++) {
      swap(arr,start_idx,i);
      permute(arr,start_idx+1,end_idx);
      swap(arr,start_idx,i);
   }
}

// main
int main() {
   int arr[] = {3,2,5};
   int size = sizeof(arr)/sizeof(arr[0]);
   cout<<"\nAll possible permutations of the given array :-\n";
   permute(arr,0,size-1);
   cout<<endl;
   return 0;
}

Back | Next

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