Friends Pairing Problem | DSA in C++ - Software Development PDF Download

Introduction

The Friends Pairing Problem is a classic problem in computer science and algorithm design. It involves finding the number of ways in which a group of friends can be paired up for a dance party. In this article, we will explore this problem and its solution using C++. We will provide multiple examples and simple code explanations to help beginners understand the concept.

Problem Statement

Given a group of friends, we need to determine the number of ways they can be paired up such that each person is paired with exactly one other person.

Approach

To solve this problem, we can use recursion or dynamic programming. Let's discuss both approaches.

Recursive Approach

The recursive approach involves breaking down the problem into smaller subproblems until we reach the base case. Here's the recursive function to solve the Friends Pairing Problem:

int countPairs(int n) {

    // Base case: If there are 0 or 1 person, no pairing is possible.

    if (n <= 1)

        return 1;

    // Case 1: The first person can be paired with any of the remaining (n-1) persons.

    int count = countPairs(n - 1);

    // Case 2: The first person can be paired with any of the remaining (n-1) persons,

    // and the remaining (n-1) persons can be paired up in countPairs(n-2) ways.

    count += (n - 1) * countPairs(n - 2);

    return count;

}

Code Explanation:

• The function 'countPairs' takes an integer 'n' as input, representing the number of friends.
• If there are 0 or 1 person, the base case is reached, and the function returns 1 since no pairing is needed.
• In Case 1, we consider the number of ways to pair the first person with the remaining (n-1) persons.
• In Case 2, we consider pairing the first person with each of the remaining (n-1) persons and recursively calculating the number of ways to pair the remaining persons.

Let's test our recursive code with a few examples:

Example 1:

int main() {

    int friends = 2;

    int pairs = countPairs(friends);

    cout << "Number of ways to pair " << friends << " friends: " << pairs << endl;

    return 0;

}

Output:

Number of ways to pair 2 friends: 2

Example 2:

int main() {

    int friends = 3;

    int pairs = countPairs(friends);

    cout << "Number of ways to pair " << friends << " friends: " << pairs << endl;

    return 0;

}

Output:

Number of ways to pair 3 friends: 4

Dynamic Programming Approach:

To optimize the solution, we can use dynamic programming to avoid redundant calculations. Here's the dynamic programming solution for the Friends Pairing Problem:

int countPairsDP(int n) {

    vector<int> dp(n + 1);

    // Base cases

    dp[0] = dp[1] = 1;

    for (int i = 2; i <= n; i++)

        dp[i] = dp[i - 1] + (i - 1) * dp[i - 2];

    return dp[n];

}

Code Explanation:

• The function 'countPairsDP' follows a bottom-up approach using an array 'dp' to store previously computed values.
• We initialize 'dp[0]' and 'dp[1]' as 1 since there is only one way to pair 0 or 1 person.
• We iterate from 2 to 'n' and calculate the number of ways to pair 'i' friends using the formula: 'dp[i] = dp[i - 1] + (i - 1) * dp[i - 2]'.

Sample Output:

Let's test our dynamic programming code with a few examples:

Example 1:

int main() {

    int friends = 2;

    int pairs = countPairsDP(friends);

    cout << "Number of ways to pair " << friends << " friends: " << pairs << endl;

    return 0;

}

Output:

Number of ways to pair 2 friends: 2

Example 2:

int main() {

    int friends = 3;

    int pairs = countPairsDP(friends);

    cout << "Number of ways to pair " << friends << " friends: " << pairs << endl;

    return 0;

}

Output:

Number of ways to pair 3 friends: 4

Sample Problems

Here are a couple of problems related to the Friends Pairing Problem that you can try to solve:

Problem 1: Given 'n' friends, find the number of ways to pair them up if some friends cannot be paired together.

Problem 2: Given 'n' friends and a list of pairs of friends who must be paired together, find the number of valid pairings.

Solution to these problems can be achieved by modifying the recursive or dynamic programming solution presented earlier.

Conclusion

The Friends Pairing Problem is a fascinating problem that can be solved using recursion or dynamic programming. In this article, we discussed both approaches and provided simple code examples to help beginners understand the concept. We also included sample problems to further enhance your understanding of the topic.