Friends pairing Problem in C++
The Friends Pairing Problem asks you to determine the total number of ways a group of n friends can be arranged, where each friend can either remain single or be paired up with one other friend. Pairings are considered unique, meaning {Alice, Bob} is the same as {Bob, Alice}. There are several approaches that can be used to solve the friends pairing problem. Some of the approaches are as follows:
Approach 1: Recursive Approach (Brute Force)
A straightforward solution involves recursion. Here's the breakdown:
Base Case: If there's only one friend (n = 1), the only option is for them to be single, so return 1.
Recursive Case: For n friends:
The nth friend can either be single (handled by the base case).
The nth friend can pair up with any of the n-1 remaining friends, leading to (n-1) possible pairings. However, each pairing creates a new group of size n-2, so we can recursively calculate the number of arrangements for that group (countFriendsPairings(n-2)).
The total number of arrangements is the sum of these two possibilities.
Example:
Let us take an example to illustrate the Friends Pairing Problem in C++ using recursive approach.
#includeusing namespace std; int countFriendsPairings(int n) { if (n <= 2) { return n; } else { return countFriendsPairings(n - 1) + (n - 1) * countFriendsPairings(n - 2); } } int main() { int n; cout << "Enter the number of friends: "; cin >> n; int totalPairings = countFriendsPairings(n); cout << "Total number of ways to arrange " << n << " friends: " << totalPairings << endl; return 0; }
Time Complexity:
The recursive approach suffers from exponential time complexity (O(2^n)) due to redundant calculations of subproblems.
Approach 2: Dynamic Programming Approach (Memoization)
We can employ Dynamic Programming (DP) with memorization to optimize the solution. This technique stores the results of subproblems to avoid recomputing them.
- Create a DP table dp to store the number of arrangements for groups of size 1 to n.
- Initialize dp[1] = 1.
- Iterate from n = 2 to n:
- dp[n] = dp[n-1] + (n-1) * dp[n-2]:
- dp[n-1] accounts for the nth friend being single.
- (n-1) * dp[n-2] accounts for pairings with the n-1 remaining friends, each leading to n-2 friends left (handled by dp[n-2]).
Example:
Let us take an example to illustrate the Friends Pairing Problem in C++ using dynamic programming approach.
#includeusing namespace std; int countFriendsPairings(int n) { int dp[n + 1]; // DP table to store arrangements for groups of size 1 to n dp[1] = 1; // Base case: 1 friend can only be single dp[2] = 2; // Base case: 2 friends can be either single or paired for (int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + (i - 1) * dp[i - 2]; } return dp[n]; } int main() { int n; cout << "Enter the number of friends: "; cin >> n; int totalPairings = countFriendsPairings(n); cout << "Total number of ways to arrange " << n << " friends: " << totalPairings << endl; return 0; }
Output:
Time and Space Complexity:
DP reduces the time complexity to O(n), significantly faster for larger n. The space complexity is O(n) due to the DP table.
Example:
For n = 3 friends:
- Recursive: It may lead to redundant calculations and potential stack overflow for larger n.
- DP: dp[1] = 1, dp[2] = dp[1] + 1 * dp[1] = 2, dp[3] = dp[2] + 2 * dp[1] = 4
Applications:
The Friends Pairing Problem in C++ finds applications in various domains, including:
Bioinformatics: Modeling possible amino acid interactions in protein folding, including paired hydrogen bonds.
Statistical Mechanics: Modeling interacting particles in systems like gases, such as molecule bonding.
Catalysis: Understanding molecule adsorption on surfaces, where molecules pair with specific sites.
Inventory Management: Determining efficient ways to group similar items, such as pairing items for storage.