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 a set with 'n' elements. Find the sum of maximum elements in all subsets of size ' p ' such that p <= n.
Consider the array { 3, 1, 5, 7 }. Here, n = 4. Let p = 3.
All possible subsets of size p = 3 are :-
{ 3, 1, 5 } ( Maximum element = 5 )
{ 3, 1, 7 } ( Maximum element = 7 )
{ 3, 5, 7 } ( Maximum element = 7 )
{ 1, 5, 7 } ( Maximum element = 7 )
Sum of maximum elements = 5 + 7 + 7 + 7 = 26

Solution :-
A naive approach to solve the problem would be to find all possible subsets of size p, extract the maximum elements from all the subsets and add them. This approach is very inefficient for large values of p and n .
The interesting thing to note here is that we need not compute all possible subsets just for getting maximum elements. We will approach the problem in a different manner.
First we will sort the array. Then, for element in each index i in the sorted array ( such that p <= i < n ), we will find out in how many subsets can the ' i 'th element appears as the maximum element.
This value is given by C ( i , p ) . We can pre-compute the values of C ( i , p ) for different values of i in a binomial matrix using the recursive formula C( n , r ) = C ( n - 1 , r - 1 ) + C ( n - 1 , r ).
See the implementation below.

#include<iostream>
#include<algorithm>
using namespace std;

/* find the sum of maximum values in all possible subsets of 
   given size
   for e.g : arr = {3,1,5,7}
   all possible subsets of size 3 are:-
   subset    max element
   {3,1,5}       5
   {3,1,7}       7
   {3,5,7}       7
   {1,5,7}       7
   Sum of max element :: 5+7+7+7 = 26
   Logic :-
   Sort the input array 'arr[]'
   Suppose array size = n & subset size = k
   For (k <= i < n), [ find the no. of times arr(i) appears as max value
   in some subsets; this value is given by C(i,k) ] and sum up all the values.
   We precompute the values of C(i,k) in a binomial matrix         
*/
int sumOfMaxValueInAllSubsets(int arr[],int size,int subset_size) {
   // sort the input array
   sort(arr,arr+size);
   // matrix to store the binomial coefficients
   // binomial[i][j] = C(i,j)
   // for e.g. binomial[4][2] = 4!/((4-2)! * 2!) = 2
   int **binomial;
   int i,j;
   int sum = 0;
   binomial = new int*[size];
   for (i=0;i<size;i++) {
      binomial[i] = new int[subset_size];
   }
   // precomputation of all binomial matrix using standard
   // recursive formula :- C(n,r) = C(n-1,r-1) + C(n-1,r)
   for (i=0;i<size;i++) {
      for (j=0;j<subset_size;j++) {
         if (i == j || j == 0) {
            //C(n,n) = C(n,0) = 1
            binomial[i][j] = 1;
         }
         else if (i < j) {
            // invalid condition
            // we are initializing it to 0
            // won't be used in actual computation 
            binomial[i][j] = 0;
         }
         else {
            // as per standard recursive formula
            binomial[i][j] = binomial[i-1][j-1] + binomial[i-1][j];
         }
      }
   }
   for (i=subset_size-1;i<size;i++) {
      // let x = binomial[i][subset_size-1]
      // then, arr[i] appears as max element in x subsets of size 'subset_size'
      // subset_size-1 denotes the array index starting from 0
      sum += arr[i]*binomial[i][subset_size-1];
   }
   return sum;
}

// main
int main() {
   int arr[] = {3,1,5,7};
   int size = sizeof(arr)/sizeof(arr[0]);
   int subset_size = 3;
   int sum = sumOfMaxValueInAllSubsets(arr,size,subset_size);
   cout<<"\nSum of max values in all subsets of size "<<subset_size <<" is "<<sum;
   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