Number of ways to Partition a Set)

#1

how to solve this problem using the concept of matrix chain multiplication??provide code

Input: n = 3
Output: Number of ways = 5
Explanation: Let the set be {1, 2, 3}
{ {1}, {2}, {3} }
{ {1}, {2, 3} }
{ {2}, {1, 3} }
{ {3}, {1, 2} }
{ {1, 2, 3} }.

#2

reply at the earliest…

#3

Matrix chain multiplication won’t be used in this case as you are breaking the set, like in this case {1,3} and {2}, instead the concept of bell numbers which is again a dp is used. Please read this article https://www.geeksforgeeks.org/bell-numbers-number-of-ways-to-partition-a-set/
it is simple dp.

#4

But matrix multiplication application can be used as we divide the problem into sets only…

#5

You are talking about matrix chain multiplication, you are breaking the chain here.
Matrices 1 and 3 can never be multiplied first and then the result is multiplied by matrice 2?

#6

I am talking about using mcm principle and then adding the results obtained…not multipling them …then we can get the result …plz code it

#7

You are not understanding it is matrix CHAIN multiplication, how are you supposed to use MCM principle when you breaking the chain? Please atleast read the article I shared. (1,3)(2) state cannot be reached from MCM

#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.