Posted on by Kalkicode
Code Dynamic Programming

Friends Pairing Problem

The Friends Pairing Problem is a well-known problem in computer science that involves pairing friends in different groups. Given a group of friends numbered from 1 to N, the task is to determine the number of ways the friends can be paired up or put into groups. The constraint is that each group can have at most two friends, and the order of friends within a group does not matter.

For example, let's consider the case where there are 5 friends (N = 5). The possible groupings are as follows:

```    (1)(2)(3)(4)(5)
(1)(2)(3) (4,5)
(1)(2) (3,4)(5)
(1)(2) (3,5)(4)
(1) (2,3)(4)(5)
(1) (2,3) (4,5)
(1) (2,4)(3)(5)
(1) (2,4) (3,5)
(1) (2,5)(4)(3)
(1) (2,5) (4,3)
(1,2)(3)(4)(5)
(1,2)(3) (4,5)
(1,2) (3,4)(5)
(1,2) (3,5)(4)
(1,3)(2)(4)(5)
(1,3)(2) (4,5)
(1,3) (2,4)(5)
(1,3) (2,5)(4)
(1,4)(3)(2)(5)
(1,4)(3) (2,5)
(1,4) (3,2)(5)
(1,4) (3,5)(2)
(1,5)(3)(4)(2)
(1,5)(3) (4,2)
(1,5) (3,4)(2)
(1,5) (3,2)(4)
```

In this example, there are 26 possible ways to pair up the 5 friends.

Now, let's discuss a solution to the Friends Pairing Problem using dynamic programming. The idea is to break down the problem into smaller subproblems and build up the solution iteratively. We'll use an array, dp[], to store the results for the subproblems.

The base cases are:

```    dp[0] = 0 (no friends)
dp[1] = 1 (one friend)
dp[2] = 2 (two friends)
```

For N greater than 2, we can determine the number of groupings by considering two possibilities for the last friend:

• The last friend can be paired up with any of the (N-1) remaining friends. In this case, the number of ways to pair up the friends will be dp[N-2]. The N-2 represents the number of friends left after considering the current friend and their pairing.
• The last friend can form a group by themselves. In this case, the number of ways to pair up the friends will be (N-1) * dp[N-1]. The (N-1) represents the number of friends that can be paired with the last friend, and dp[N-1] represents the number of ways to pair up the remaining (N-1) friends.

Therefore, the recurrence relation for dp[N] (the number of ways to pair up N friends) can be defined as:

```    dp[N] = dp[N-1] + (N-1) * dp[N-2]
```

We can calculate the dp[N] values iteratively for N ranging from 3 to the given input value. The final result will be stored in dp[n], where n is the input value.

The time complexity of this solution is O(n), as we need to calculate dp[N] for each N from 3 to n. The space complexity is also O(n) since we are using an array of size n+1 to store the results.

Code solution

``````/*
Java program for
Friends Pairing Problem
*/
public class Pairing
{
public void firendPairing(int n)
{
// Auxiliary space
int[] dp = new int[n + 1];
for (int i = 0; i <= n; i++)
{
if (i <= 2)
{
// When i less than 3
dp[i] = i;
}
else
{
dp[i] = dp[i - 1] + ((i - 1) * dp[i - 2]);
}
}
System.out.println(" Given N : " + n);
System.out.println(" Number of groups : " + dp[n]);
}
public static void main(String[] args)
{
int n = 5;
/*
n = 5
------------
(1)(2)(3)(4)(5)
(1)(2)(3) (4,5)
(1)(2) (3,4)(5)
(1)(2) (3,5)(4)
(1) (2,3)(4)(5)
(1) (2,3) (4,5)
(1) (2,4)(3)(5)
(1) (2,4) (3,5)
(1) (2,5)(4)(3)
(1) (2,5) (4,3)
(1,2)(3)(4)(5)
(1,2)(3) (4,5)
(1,2) (3,4)(5)
(1,2) (3,5)(4)
(1,3)(2)(4)(5)
(1,3)(2) (4,5)
(1,3) (2,4)(5)
(1,3) (2,5)(4)
(1,4)(3)(2)(5)
(1,4)(3) (2,5)
(1,4) (3,2)(5)
(1,4) (3,5)(2)
(1,5)(3)(4)(2)
(1,5)(3) (4,2)
(1,5) (3,4)(2)
(1,5) (3,2)(4)
*/
n = 3;
/*
n = 3
------------
1 : (1)(2)(3)
2 : (1) (2,3)
3 :  (1,2)(3)
4 :  (1,3)(2)
*/
}
}``````

Output

`````` Given N : 5
Number of groups : 26
Given N : 3
Number of groups : 4``````
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ program for
Friends Pairing Problem
*/
class Pairing
{
public: void firendPairing(int n)
{
// Auxiliary space
int dp[n + 1];
for (int i = 0; i <= n; i++)
{
if (i <= 2)
{
// When i less than 3
dp[i] = i;
}
else
{
dp[i] = dp[i - 1] + ((i - 1) *dp[i - 2]);
}
}
cout << " Given N : " << n << endl;
cout << " Number of groups : " << dp[n] << endl;
}
};
int main()
{
int n = 5;
/*
n = 5
------------
(1)(2)(3)(4)(5)
(1)(2)(3) (4,5)
(1)(2) (3,4)(5)
(1)(2) (3,5)(4)
(1) (2,3)(4)(5)
(1) (2,3) (4,5)
(1) (2,4)(3)(5)
(1) (2,4) (3,5)
(1) (2,5)(4)(3)
(1) (2,5) (4,3)
(1,2)(3)(4)(5)
(1,2)(3) (4,5)
(1,2) (3,4)(5)
(1,2) (3,5)(4)
(1,3)(2)(4)(5)
(1,3)(2) (4,5)
(1,3) (2,4)(5)
(1,3) (2,5)(4)
(1,4)(3)(2)(5)
(1,4)(3) (2,5)
(1,4) (3,2)(5)
(1,4) (3,5)(2)
(1,5)(3)(4)(2)
(1,5)(3) (4,2)
(1,5) (3,4)(2)
(1,5) (3,2)(4)
*/
n = 3;
/*
n = 3
------------
1 : (1)(2)(3)
2 : (1) (2,3)
3 :  (1,2)(3)
4 :  (1,3)(2)
*/
return 0;
}``````

Output

`````` Given N : 5
Number of groups : 26
Given N : 3
Number of groups : 4``````
``````// Include namespace system
using System;
/*
Csharp program for
Friends Pairing Problem
*/
public class Pairing
{
public void firendPairing(int n)
{
// Auxiliary space
int[] dp = new int[n + 1];
for (int i = 0; i <= n; i++)
{
if (i <= 2)
{
// When i less than 3
dp[i] = i;
}
else
{
dp[i] = dp[i - 1] + ((i - 1) * dp[i - 2]);
}
}
Console.WriteLine(" Given N : " + n);
Console.WriteLine(" Number of groups : " + dp[n]);
}
public static void Main(String[] args)
{
int n = 5;
/*
n = 5
------------
(1)(2)(3)(4)(5)
(1)(2)(3) (4,5)
(1)(2) (3,4)(5)
(1)(2) (3,5)(4)
(1) (2,3)(4)(5)
(1) (2,3) (4,5)
(1) (2,4)(3)(5)
(1) (2,4) (3,5)
(1) (2,5)(4)(3)
(1) (2,5) (4,3)
(1,2)(3)(4)(5)
(1,2)(3) (4,5)
(1,2) (3,4)(5)
(1,2) (3,5)(4)
(1,3)(2)(4)(5)
(1,3)(2) (4,5)
(1,3) (2,4)(5)
(1,3) (2,5)(4)
(1,4)(3)(2)(5)
(1,4)(3) (2,5)
(1,4) (3,2)(5)
(1,4) (3,5)(2)
(1,5)(3)(4)(2)
(1,5)(3) (4,2)
(1,5) (3,4)(2)
(1,5) (3,2)(4)
*/
n = 3;
/*
n = 3
------------
1 : (1)(2)(3)
2 : (1) (2,3)
3 :  (1,2)(3)
4 :  (1,3)(2)
*/
}
}``````

Output

`````` Given N : 5
Number of groups : 26
Given N : 3
Number of groups : 4``````
``````package main
import "fmt"
/*
Go program for
Friends Pairing Problem
*/

func firendPairing(n int) {
// Auxiliary space
var dp = make([] int, n + 1)
for i := 0 ; i <= n ; i++ {
if i <= 2 {
// When i less than 3
dp[i] = i
} else {
dp[i] = dp[i - 1] + ((i - 1) * dp[i - 2])
}
}
fmt.Println(" Given N : ", n)
fmt.Println(" Number of groups : ", dp[n])
}
func main() {

var n int = 5
/*
n = 5
------------
(1)(2)(3)(4)(5)
(1)(2)(3) (4,5)
(1)(2) (3,4)(5)
(1)(2) (3,5)(4)
(1) (2,3)(4)(5)
(1) (2,3) (4,5)
(1) (2,4)(3)(5)
(1) (2,4) (3,5)
(1) (2,5)(4)(3)
(1) (2,5) (4,3)
(1,2)(3)(4)(5)
(1,2)(3) (4,5)
(1,2) (3,4)(5)
(1,2) (3,5)(4)
(1,3)(2)(4)(5)
(1,3)(2) (4,5)
(1,3) (2,4)(5)
(1,3) (2,5)(4)
(1,4)(3)(2)(5)
(1,4)(3) (2,5)
(1,4) (3,2)(5)
(1,4) (3,5)(2)
(1,5)(3)(4)(2)
(1,5)(3) (4,2)
(1,5) (3,4)(2)
(1,5) (3,2)(4)
*/
firendPairing(n)
n = 3
/*
n = 3
------------
1 : (1)(2)(3)
2 : (1) (2,3)
3 :  (1,2)(3)
4 :  (1,3)(2)
*/
firendPairing(n)
}``````

Output

`````` Given N : 5
Number of groups : 26
Given N : 3
Number of groups : 4``````
``````<?php
/*
Php program for
Friends Pairing Problem
*/
class Pairing
{
public	function firendPairing(\$n)
{
// Auxiliary space
\$dp = array_fill(0, \$n + 1, 0);
for (\$i = 0; \$i <= \$n; \$i++)
{
if (\$i <= 2)
{
// When i less than 3
\$dp[\$i] = \$i;
}
else
{
\$dp[\$i] = \$dp[\$i - 1] + ((\$i - 1) * \$dp[\$i - 2]);
}
}
echo(" Given N : ".\$n.
"\n");
echo(" Number of groups : ".\$dp[\$n].
"\n");
}
}

function main()
{
\$n = 5;
/*
n = 5
------------
(1)(2)(3)(4)(5)
(1)(2)(3) (4,5)
(1)(2) (3,4)(5)
(1)(2) (3,5)(4)
(1) (2,3)(4)(5)
(1) (2,3) (4,5)
(1) (2,4)(3)(5)
(1) (2,4) (3,5)
(1) (2,5)(4)(3)
(1) (2,5) (4,3)
(1,2)(3)(4)(5)
(1,2)(3) (4,5)
(1,2) (3,4)(5)
(1,2) (3,5)(4)
(1,3)(2)(4)(5)
(1,3)(2) (4,5)
(1,3) (2,4)(5)
(1,3) (2,5)(4)
(1,4)(3)(2)(5)
(1,4)(3) (2,5)
(1,4) (3,2)(5)
(1,4) (3,5)(2)
(1,5)(3)(4)(2)
(1,5)(3) (4,2)
(1,5) (3,4)(2)
(1,5) (3,2)(4)
*/
\$n = 3;
/*
n = 3
------------
1 : (1)(2)(3)
2 : (1) (2,3)
3 :  (1,2)(3)
4 :  (1,3)(2)
*/
}
main();``````

Output

`````` Given N : 5
Number of groups : 26
Given N : 3
Number of groups : 4``````
``````/*
Node JS program for
Friends Pairing Problem
*/
class Pairing
{
firendPairing(n)
{
// Auxiliary space
var dp = Array(n + 1).fill(0);
for (var i = 0; i <= n; i++)
{
if (i <= 2)
{
// When i less than 3
dp[i] = i;
}
else
{
dp[i] = dp[i - 1] + ((i - 1) * dp[i - 2]);
}
}
console.log(" Given N : " + n);
console.log(" Number of groups : " + dp[n]);
}
}

function main()
{
var n = 5;
/*
n = 5
------------
(1)(2)(3)(4)(5)
(1)(2)(3) (4,5)
(1)(2) (3,4)(5)
(1)(2) (3,5)(4)
(1) (2,3)(4)(5)
(1) (2,3) (4,5)
(1) (2,4)(3)(5)
(1) (2,4) (3,5)
(1) (2,5)(4)(3)
(1) (2,5) (4,3)
(1,2)(3)(4)(5)
(1,2)(3) (4,5)
(1,2) (3,4)(5)
(1,2) (3,5)(4)
(1,3)(2)(4)(5)
(1,3)(2) (4,5)
(1,3) (2,4)(5)
(1,3) (2,5)(4)
(1,4)(3)(2)(5)
(1,4)(3) (2,5)
(1,4) (3,2)(5)
(1,4) (3,5)(2)
(1,5)(3)(4)(2)
(1,5)(3) (4,2)
(1,5) (3,4)(2)
(1,5) (3,2)(4)
*/
n = 3;
/*
n = 3
------------
1 : (1)(2)(3)
2 : (1) (2,3)
3 :  (1,2)(3)
4 :  (1,3)(2)
*/
}
main();``````

Output

`````` Given N : 5
Number of groups : 26
Given N : 3
Number of groups : 4``````
``````#    Python 3 program for
#    Friends Pairing Problem
class Pairing :
def firendPairing(self, n) :
#  Auxiliary space
dp = [0] * (n + 1)
i = 0
while (i <= n) :
if (i <= 2) :
#  When i less than 3
dp[i] = i
else :
dp[i] = dp[i - 1] + ((i - 1) * dp[i - 2])

i += 1

print(" Given N : ", n)
print(" Number of groups : ", dp[n])

def main() :
n = 5
#    n = 5
#    ------------
#    (1)(2)(3)(4)(5)
#    (1)(2)(3) (4,5)
#    (1)(2) (3,4)(5)
#    (1)(2) (3,5)(4)
#    (1) (2,3)(4)(5)
#    (1) (2,3) (4,5)
#    (1) (2,4)(3)(5)
#    (1) (2,4) (3,5)
#    (1) (2,5)(4)(3)
#    (1) (2,5) (4,3)
#    (1,2)(3)(4)(5)
#    (1,2)(3) (4,5)
#    (1,2) (3,4)(5)
#    (1,2) (3,5)(4)
#    (1,3)(2)(4)(5)
#    (1,3)(2) (4,5)
#    (1,3) (2,4)(5)
#    (1,3) (2,5)(4)
#    (1,4)(3)(2)(5)
#    (1,4)(3) (2,5)
#    (1,4) (3,2)(5)
#    (1,4) (3,5)(2)
#    (1,5)(3)(4)(2)
#    (1,5)(3) (4,2)
#    (1,5) (3,4)(2)
#    (1,5) (3,2)(4)
n = 3
#    n = 3
#    ------------
#    1 : (1)(2)(3)
#    2 : (1) (2,3)
#    3 :  (1,2)(3)
#    4 :  (1,3)(2)

if __name__ == "__main__": main()``````

Output

`````` Given N :  5
Number of groups :  26
Given N :  3
Number of groups :  4``````
``````#    Ruby program for
#    Friends Pairing Problem
class Pairing
def firendPairing(n)
#  Auxiliary space
dp = Array.new(n + 1) {0}
i = 0
while (i <= n)
if (i <= 2)
#  When i less than 3
dp[i] = i
else

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

i += 1
end

print(" Given N : ", n, "\n")
print(" Number of groups : ", dp[n], "\n")
end

end

def main()
n = 5
#    n = 5
#    ------------
#    (1)(2)(3)(4)(5)
#    (1)(2)(3) (4,5)
#    (1)(2) (3,4)(5)
#    (1)(2) (3,5)(4)
#    (1) (2,3)(4)(5)
#    (1) (2,3) (4,5)
#    (1) (2,4)(3)(5)
#    (1) (2,4) (3,5)
#    (1) (2,5)(4)(3)
#    (1) (2,5) (4,3)
#    (1,2)(3)(4)(5)
#    (1,2)(3) (4,5)
#    (1,2) (3,4)(5)
#    (1,2) (3,5)(4)
#    (1,3)(2)(4)(5)
#    (1,3)(2) (4,5)
#    (1,3) (2,4)(5)
#    (1,3) (2,5)(4)
#    (1,4)(3)(2)(5)
#    (1,4)(3) (2,5)
#    (1,4) (3,2)(5)
#    (1,4) (3,5)(2)
#    (1,5)(3)(4)(2)
#    (1,5)(3) (4,2)
#    (1,5) (3,4)(2)
#    (1,5) (3,2)(4)
n = 3
#    n = 3
#    ------------
#    1 : (1)(2)(3)
#    2 : (1) (2,3)
#    3 :  (1,2)(3)
#    4 :  (1,3)(2)
end

main()``````

Output

`````` Given N : 5
Number of groups : 26
Given N : 3
Number of groups : 4
``````
``````/*
Scala program for
Friends Pairing Problem
*/
class Pairing()
{
def firendPairing(n: Int): Unit = {
// Auxiliary space
var dp: Array[Int] = Array.fill[Int](n + 1)(0);
var i: Int = 0;
while (i <= n)
{
if (i <= 2)
{
// When i less than 3
dp(i) = i;
}
else
{
dp(i) = dp(i - 1) + ((i - 1) * dp(i - 2));
}
i += 1;
}
println(" Given N : " + n);
println(" Number of groups : " + dp(n));
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Pairing = new Pairing();
var n: Int = 5;
/*
n = 5
------------
(1)(2)(3)(4)(5)
(1)(2)(3) (4,5)
(1)(2) (3,4)(5)
(1)(2) (3,5)(4)
(1) (2,3)(4)(5)
(1) (2,3) (4,5)
(1) (2,4)(3)(5)
(1) (2,4) (3,5)
(1) (2,5)(4)(3)
(1) (2,5) (4,3)
(1,2)(3)(4)(5)
(1,2)(3) (4,5)
(1,2) (3,4)(5)
(1,2) (3,5)(4)
(1,3)(2)(4)(5)
(1,3)(2) (4,5)
(1,3) (2,4)(5)
(1,3) (2,5)(4)
(1,4)(3)(2)(5)
(1,4)(3) (2,5)
(1,4) (3,2)(5)
(1,4) (3,5)(2)
(1,5)(3)(4)(2)
(1,5)(3) (4,2)
(1,5) (3,4)(2)
(1,5) (3,2)(4)
*/
n = 3;
/*
n = 3
------------
1 : (1)(2)(3)
2 : (1) (2,3)
3 :  (1,2)(3)
4 :  (1,3)(2)
*/
}
}``````

Output

`````` Given N : 5
Number of groups : 26
Given N : 3
Number of groups : 4``````
``````/*
Swift 4 program for
Friends Pairing Problem
*/
class Pairing
{
func firendPairing(_ n: Int)
{
// Auxiliary space
var dp: [Int] = Array(repeating: 0, count: n + 1);
var i: Int = 0;
while (i <= n)
{
if (i <= 2)
{
// When i less than 3
dp[i] = i;
}
else
{
dp[i] = dp[i - 1] + ((i - 1) * dp[i - 2]);
}
i += 1;
}
print(" Given N : ", n);
print(" Number of groups : ", dp[n]);
}
}
func main()
{
var n: Int = 5;
/*
n = 5
------------
(1)(2)(3)(4)(5)
(1)(2)(3) (4,5)
(1)(2) (3,4)(5)
(1)(2) (3,5)(4)
(1) (2,3)(4)(5)
(1) (2,3) (4,5)
(1) (2,4)(3)(5)
(1) (2,4) (3,5)
(1) (2,5)(4)(3)
(1) (2,5) (4,3)
(1,2)(3)(4)(5)
(1,2)(3) (4,5)
(1,2) (3,4)(5)
(1,2) (3,5)(4)
(1,3)(2)(4)(5)
(1,3)(2) (4,5)
(1,3) (2,4)(5)
(1,3) (2,5)(4)
(1,4)(3)(2)(5)
(1,4)(3) (2,5)
(1,4) (3,2)(5)
(1,4) (3,5)(2)
(1,5)(3)(4)(2)
(1,5)(3) (4,2)
(1,5) (3,4)(2)
(1,5) (3,2)(4)
*/
n = 3;
/*
n = 3
------------
1 : (1)(2)(3)
2 : (1) (2,3)
3 :  (1,2)(3)
4 :  (1,3)(2)
*/
}
main();``````

Output

`````` Given N :  5
Number of groups :  26
Given N :  3
Number of groups :  4``````
``````/*
Kotlin program for
Friends Pairing Problem
*/
class Pairing
{
fun firendPairing(n: Int): Unit
{
// Auxiliary space
var dp: Array < Int > = Array(n + 1)
{
0
};
var i: Int = 0;
while (i <= n)
{
if (i <= 2)
{
// When i less than 3
dp[i] = i;
}
else
{
dp[i] = dp[i - 1] + ((i - 1) * dp[i - 2]);
}
i += 1;
}
println(" Given N : " + n);
println(" Number of groups : " + dp[n]);
}
}
fun main(args: Array < String > ): Unit
{
var n: Int = 5;
/*
n = 5
------------
(1)(2)(3)(4)(5)
(1)(2)(3) (4,5)
(1)(2) (3,4)(5)
(1)(2) (3,5)(4)
(1) (2,3)(4)(5)
(1) (2,3) (4,5)
(1) (2,4)(3)(5)
(1) (2,4) (3,5)
(1) (2,5)(4)(3)
(1) (2,5) (4,3)
(1,2)(3)(4)(5)
(1,2)(3) (4,5)
(1,2) (3,4)(5)
(1,2) (3,5)(4)
(1,3)(2)(4)(5)
(1,3)(2) (4,5)
(1,3) (2,4)(5)
(1,3) (2,5)(4)
(1,4)(3)(2)(5)
(1,4)(3) (2,5)
(1,4) (3,2)(5)
(1,4) (3,5)(2)
(1,5)(3)(4)(2)
(1,5)(3) (4,2)
(1,5) (3,4)(2)
(1,5) (3,2)(4)
*/
n = 3;
/*
n = 3
------------
1 : (1)(2)(3)
2 : (1) (2,3)
3 :  (1,2)(3)
4 :  (1,3)(2)
*/
}``````

Output

`````` Given N : 5
Number of groups : 26
Given N : 3
Number of groups : 4``````

we discussed the Friends Pairing Problem and provided a solution using dynamic programming. We explained the problem statement, presented an approach to solve it, and provided a Java implementation for the solution. The time and space complexities of the solution were also discussed.

The Friends Pairing Problem is an interesting problem that can be solved using dynamic programming techniques. It has applications in various scenarios where groups or pairings need to be formed. The solution we presented provides an efficient way to calculate the number of possible groupings for a given number of friends.

By understanding the problem and implementing the solution, you now have a tool to solve the Friends Pairing Problem and explore related scenarios where grouping or pairing is required.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post