Python - Friends Pairing Problem

Python – Friends Pairing Problem

The Friends Pairing Problem is a classic dynamic programming challenge. Given n friends, each friend can either remain single or be paired up with another friend. The goal is to count the total number of ways in which the friends can be paired or left single.

Problem Statement

For a given number of friends n, find the number of ways they can remain single or be paired up. Each friend can only be part of one pair.

The recurrence relation for this problem is:

F(n) = F(n-1) + (n-1) * F(n-2)

Where:

F(n-1): The n^th friend remains single, so we count the arrangements for the remaining n-1 friends.
(n-1) * F(n-2): The n^th friend pairs up with any one of the remaining n-1 friends, and the remaining n-2 friends are arranged in F(n-2) ways.

The base cases for the problem are:

F(0) = 1 (No friends, one way to arrange nothing)
F(1) = 1 (One friend remains single)

Sample Input and Output

Example 1:

</>

Copy

# Input:
n = 3

# Calculation:
# F(3) = F(2) + 2 * F(1)
# F(2) = F(1) + 1 * F(0) = 1 + 1 = 2
# Therefore, F(3) = 2 + 2 * 1 = 4

# Output:
4

Explanation: For 3 friends, there are 4 possible arrangements:

All three remain single.
Friend 1 pairs with Friend 2 while Friend 3 remains single.
Friend 1 pairs with Friend 3 while Friend 2 remains single.
Friend 2 pairs with Friend 3 while Friend 1 remains single.

Example 2:

</>

Copy

# Input:
n = 4

# Calculation:
# F(4) = F(3) + 3 * F(2)
# From Example 1, F(3) = 4 and F(2) = 2
# Therefore, F(4) = 4 + 3 * 2 = 10

# Output:
10

Explanation: For 4 friends, there are 10 possible arrangements. This is computed by considering both the cases where a friend remains single and where a friend pairs up with any of the other 3 friends.

Solution Approach

We will solve the Friends Pairing Problem using dynamic programming. Two common approaches are:

Recursive Approach with Memoization: Recursively compute F(n) while caching the results to avoid redundant computations.
Iterative Dynamic Programming: Build a solution in a bottom-up manner using an array or table to store intermediate results.

Python Program

Method 1: Recursive Approach with Memoization

</>

Copy

def friends_pairing_recursive(n, memo=None):
    """
    Compute the number of ways to arrange n friends as either single or paired using recursion with memoization.
    
    Parameters:
    n (int): Number of friends.
    memo (dict): Cache to store computed results.
    
    Returns:
    int: Number of possible arrangements.
    """
    if memo is None:
        memo = {}
        
    # Base cases: if 0 or 1 friend, only 1 arrangement is possible.
    if n <= 1:
        return 1
    
    # Return cached result if it exists.
    if n in memo:
        return memo[n]
    
    # Recurrence relation: F(n) = F(n-1) + (n-1) * F(n-2)
    memo[n] = friends_pairing_recursive(n - 1, memo) + (n - 1) * friends_pairing_recursive(n - 2, memo)
    return memo[n]

# Test examples
print("Method 1 - Recursive with Memoization")
print("Number of arrangements for 3 friends:", friends_pairing_recursive(3))  # Expected output: 4
print("Number of arrangements for 4 friends:", friends_pairing_recursive(4))  # Expected output: 10

Explanation: This method recursively breaks down the problem by deciding whether the n^th friend stays single or pairs up. The use of memoization caches intermediate results, thus preventing repeated calculations and significantly improving efficiency.

Method 2: Iterative Dynamic Programming

</>

Copy

def friends_pairing_iterative(n):
    """
    Compute the number of ways to arrange n friends using an iterative dynamic programming approach.
    
    Parameters:
    n (int): Number of friends.
    
    Returns:
    int: Number of possible arrangements.
    """
    # Base cases: if 0 or 1 friend, only 1 arrangement exists.
    if n <= 1:
        return 1

    # Create a list to store results for 0 to n friends.
    dp = [0] * (n + 1)
    dp[0], dp[1] = 1, 1

    # Build the solution iteratively using the recurrence relation.
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + (i - 1) * dp[i - 2]
    
    return dp[n]

# Test examples
print("\nMethod 2 - Iterative Dynamic Programming")
print("Number of arrangements for 3 friends:", friends_pairing_iterative(3))  # Expected output: 4
print("Number of arrangements for 4 friends:", friends_pairing_iterative(4))  # Expected output: 10

Explanation: This iterative approach builds a DP table (or list) dp where each dp[i] represents the number of arrangements for i friends. Starting from the base cases, the table is filled using the recurrence relation. This bottom-up method avoids the overhead of recursion while efficiently computing the final answer.

Conclusion

In this tutorial, we tackled the Friends Pairing Problem using dynamic programming. We explored two effective approaches:

Recursive with Memoization: Breaks the problem into subproblems and caches results to optimize performance.
Iterative Dynamic Programming: Uses a bottom-up approach to build the solution iteratively in a DP table.

Both methods are efficient and useful for solving the Friends Pairing Problem. Choose the one that best fits your interview requirements and coding style.

TutorialKart

Python – Friends Pairing Problem