Problem
Given a Set of jars of candies, what is the number of ways of getting a pair of candies such that they belong from different jars.
For example given {{1,2}, {3,4}, {6}}. The answer is 8({1,3},{1,4},{1,6},{2,3},{2,4},{2,6},{3,6}, {4,6}).
Solution
Let m be the number of jars with 2, n be the number of jars with 1
The total combinations are C(n, 2) + C(m, 2) + C(m, 1) * C(n, 1)
if n < 2, then C(n, 2) = 0;
if m < 2, then C(m, 2) = 0;
if n < 1, then C(n, 1) = 0;
if m < 1, then C(m, 1) = 0;
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Compute the jar pair combinations
Created Date : 07-August-2013
Last Modified :
===========================================================================
*/
#include <vector>
#include <iostream>
#include <iomanip>
using namespace std;
int ComputeJarCombination(vector<int>& v )
{
int sum(0);
for(int i = 0; i < v.size() - 1; i ++){
for(int j = i + 1; j < v.size(); j++){
sum += v[i] * v[j];
}
}
return sum;
}
void DoTest(vector<int> &v)
{
cout << "The input array is " << endl;
for(int i = 0; i < v.size(); ++i){
cout << setw(4) << v[i];
}
cout << endl;
int sum = ComputeJarCombination(v);
cout << "The total combination is " << sum << endl;
}
int main(int argc, char* argv[])
{
int arr[] = {2, 2, 1} ;
vector<int> v(arr, arr + sizeof(arr)/sizeof(int));
DoTest(v);
int arr1[] = {2, 1, 1} ;
vector<int> v1(arr1, arr1 + sizeof(arr1)/sizeof(int));
DoTest(v1);
int arr2[] = {1, 1, 1} ;
vector<int> v2(arr2, arr2 + sizeof(arr2)/sizeof(int));
DoTest(v2);
int arr3[] = {1} ;
vector<int> v3(arr3, arr3 + sizeof(arr3)/sizeof(int));
DoTest(v3);
int arr4[] = {2} ;
vector<int> v4(arr4, arr4 + sizeof(arr4)/sizeof(int));
DoTest(v4);
int arr5[] = {1, 2} ;
vector<int> v5(arr5, arr5 + sizeof(arr5)/sizeof(int));
DoTest(v5);
return 0;
}
Output
The input array is
2 2 1
The total combination is 8
The input array is
2 1 1
The total combination is 5
The input array is
1 1 1
The total combination is 3
The input array is
1
The total combination is 0
The input array is
2
The total combination is 0
The input array is
1 2
The total combination is 2
Press any key to continue . . .