লংগেস্ট কমন সাব-সিকুয়েন্স (Longest Common Subsequence)

২ টি স্ট্রিং দেয়া থাকবে। এদের মাঝে ম্যাক্সিমাম কত দৈর্ঘ্যের সাব-সিকুয়েন্স আছে, এবং সিকুয়েন্সটি কি, এটা আমাদের বের করতে হবে।
সাব-সিকুয়েন্স হল এমন একটি সিকুয়েন্স, যা কিনা ২ টি স্ট্রিং এর মাঝে কমন ক্যারেক্টার নিয়ে তৈরী এবং, একটি ক্যারেক্টার এর ইনডেক্স এর চেয়ে পরের ক্যারেক্টার এর ইনডেক্স (একটি নির্দিষ্ট স্ট্রিং) অবশ্যই বড় হবে।
যেমনঃ
String X = "AAABCD"
String Y = "ABCDDA"
তাহলে, এদের মাঝে LCS হবেঃ "ABCD"
ধরি Z = "ABCD"
এখানে দেখা যাচ্ছে যে, A,B,C,D এর প্রত্যেকটি ক্যারেক্টার এর ইনডেক্স তার আগের ক্যারেক্টার থেকে বড় (X এবং Y উভয় স্ট্রিং এ)। আমরা মেইনলি ক্যারেক্টার এর অর্ডার মেইনটেইন করবো।

এপ্রোচঃ প্রথমে আমরা X এর i-তম prefix (ক্যারেক্টার, যা অন্য ক্যারেক্টার এর আগে বসাই) কে Xi দিয়ে প্রকাশ করি। তাহলে,
X1 = "A"
X3 = "AAA" etc..
এখন আমরা খেয়াল করি,

• যদি, Xi == Yj হয়, (অর্থাৎ ২ টি স্ট্রিং এর ক্যারেক্টার মিলে গেছে), তাহলে, Zs = Xi = Yj হবে, এবং Zs-1, Xi-1 এবং Yj-1 এর একটি LCS হবে
• যদি, Xi != Yj হয়, তাহলে Zs != Xi বলতে আমরা বুঝাবো, ্Z , Xi-1 এবং Yj এর একটি LCS
• যদি, Xi != Yj হয়, তাহলে Zs != Yj বলতে আমরা বুঝাবো, ্Z , Xi এবং Yj-1 এর একটি LCS

তাহলে, যখন ক্যারেক্টার সমান হবে না, তখন আমরা ২ স্ট্রিং এর মাঝে ক্যালকুলেট করে ম্যাক্সিমাম মানকে নিবো।তাহলে আমাদের অ্যালগরিদম অনেকটা এরকমঃ

c[ i,j ] = 0; if i == 0 OR j == 0
              c[ i-1,j-1 ] + 1; if i,j > 0 AND Xi == Yj
              max ( c[ i,j-1 ], c[ i-1,j ] ); if i,j > 0 AND Xi != Yj

LCS ক্যালকুলেশন

ধরি, X = "ABCBDAB", Y = "BDCABA"
এখন আমরা একটি 8x7 সাইজ এর ২-ডি অ্যারে নিবো। 8 = X.size()+1, 7 = Y.size()+1

আমাদের অ্যারের [0,0] ইনডেক্স 0 ইনিশিয়ালাইজ করবো। এরপরে আমরা প্রতি সারি-কলামে ২ টি স্ট্রিং থেকে ভ্যালু মিলানোর চেষ্টা করবো। এবং আমাদের অ্যালগরিদম অনুযায়ী মান বসাবো। এখন খেয়াল করে দেখবো যে, ইনডেক্স ১ এর A(String X) এর সাথে ইনডেক্স ১ এর B (String Y) মিলেনি, কাজেই আমরা [1,1] ইনডেক্স এ 0 বসিয়ে দিলাম। এই 0 এসেছে, [1,0] এবং [0,1] ইনডেক্স এর ভ্যালুর মাঝের ম্যাক্সিমাম ভ্যালু। অর্থাৎ max ([1,0] এবং [0,1]) = 0।

এর মানে হল, X1 এবং Y1 এর মাঝে LCS এর দৈর্ঘ্য = 0. এভাবে আমরা টেবিল ফিল আপ করতে থাকি।

এখানে, 1(A) এর সাথে 4(A) মিলে গেছে, তাই আমরা [0,3] ঘরের ভ্যালু + ১ বসাবো। এভাবে আমরা বাকি ভ্যালুর জন্য ঘর ফিল আপ করলে এরকম একটি ফাইনাল টেবিল পাবো।

কাজেই, আমাদের LCS স্ট্রিং এর দৈর্ঘ্য হচ্ছে 4.
কোডঃ

এখন আমাদের কাজ হবে, এই যে LCS স্ট্রিং টির দৈর্ঘ্য পেলাম, একে প্রিন্ট করা। এর জন্য আমাদের পাথ বের করতে হবে। আমরা আমাদের ফাইনাল রেজাল্ট থেকে উপরে এবং বামে মুভ করতে থাকবো, যখন আমরা দেখবো যে Xi == Yj, তখন আমরা সেই ঘরের ভ্যালু প্রিন্ট করে দিবো। আমরা যদি পাথ ফাইন্ডিং এর জন্য টেবিল জেনারেট করি, দেখতে এরকম হবে ফাইনালিঃ

এই হচ্ছে আমাদের ফাইনাল পাথ টেবিল। আমরা নিচ থেকে উপরে সিকুয়েন্স অনুযায়ী উঠতে থাকবো। আমরা LCS বের করার সময়, যখন অ্যারেতে ভ্যালু আপডেট করতাম, ঐ সময়, আমরা আমাদের পাথ টেবিল ও আপডেট করে দিবো। Xi == Yj হলে আমরা টেবিলে স্টোর করবো m, তানাহলে, আমাদের চেক করতে হবে যে c[i-1,j] কি c[i,j-1] থেকে বড় অথবা সমান কিনা। এক্সদি বড় অথবা সমান হয়, তাহলে আমরা স্টোর করবো u (up), তানাহলে, আমরা l(left) স্টোর করবো। তাহলে আমাদের LCS স্ট্রিং: "BCBA" এরপরে আমরা নিচের কোড অনুযায়ী পাথ ক্যালকুলেট করবোঃ

এখানে char x[] হল X স্ট্রিং, আমরা এখানে ইচ্ছা করলে Y ও পাঠাতে পারতাম। যেহেতু, ২ স্ট্রিং এর মাঝের কমন স্ট্রিং বের করতে চাচ্ছি, কাজেই, আমাদের ২ টি স্ট্রিং চেক না করে একটির ইনডেক্স চেক করলেই কাজ হয়ে যাচ্ছে

প্র্যাকটিস প্রব্লেম (Practice Problems)

• Uva: 10192 - Vacation
• Uva: 10405 - Longest Common Subsequence
• Uva: 10635 - Prince and Princess
• Hacker Earth: Longest Common Subsequence
• Hackerrank: LCS Returns
• Light Oj: An Easy LCS
• Spoj: Cross country
• Codechef: Chef and LCS

ম্যাট্রিক্স চেইন মালটিপ্লিকেশন (Matrix Chain Multiplication)

আমাদের কিছু ম্যাট্রিক্স দেয়া থাকবে।আমাদেরকে বের করতে হবে, এমন কোন অর্ডার এ ম্যাট্রিক্সগুলিকে গুন করলে তাদের cost মিনিমাম হবে।
ধরি আমাদের ২ টি ম্যাট্রিক্স দেয়া আছে A এবং B.
এখন A = [ P x Q ] ; এখানে P হল সারি (row), Q হল কলাম (column)
B = [ Q x R ]
এখন A*B করার পরে আমরা যে নতুন ম্যাট্রিক্স পাবো, তার ডাইমেনশন হবে = P x R
এখন আমাদের সবসময় লক্ষ্য রাখতে হবে যে ২ টি ম্যাট্রিক্স এর গুনের জন্য অবশ্যই প্রথম ম্যাট্রিক্স এর কলাম এবং দ্বিতীয় ম্যাট্রিক্স এর সারি সমান হতে হবে। এবং এক্ষেত্রে তাদের মাঝে গুনের জন্য টোটাল মালটিপ্লিকেশন লাগবে ঃ P*Q*R; [ ১ম ম্যাট্রিক্স এর সারি * ১ম ম্যাট্রিক্স এর কলাম * ২য় ম্যাট্রিক্স এর কলাম ]।
অর্থাৎ, cost = P*Q*R.

এবং আমাদের কাজ হচ্ছে একাধিক ম্যাট্রিক্স এভাবে লিনিয়ারলি গুন করা যাতে তাদের cost মিনিমাম হয়।
এখানে মূল ব্যাপার হল, আমরা যেভাবেই মালটিপ্লাই করিনা কেন, ফাইনাল রেজাল্ট সবসময় একই আসবে। অর্থাৎ গুন করার ক্ষেত্রে অর্ডার কোন প্রভাব ফেলেনা। তবে একেক অর্ডার এর জন্য একেকরকম cost আসবে। আমাদের কাজ হবে এমন অর্ডার বের করা যাতে cost মিনিমাম হয়।

ধরি, A [10 x 100 ] , B [ 100 x 5 ] , C [ 5 x 50 ], এই তিনটি ম্যাট্রিক্স। এখন আমরা ২ ভাবে এদের গুন করতে পারি।

• ( A * B ) * C
• A * ( B * C )

এখন ( A * B ) * C এর ক্ষেত্রে, প্রথমে,
( A * B ) এর জন্য cost, c1 = 10 * 100 * 5 = 5000; [ cost = P*Q*R ]
এখন ( A * B ) করার পরে আমরা যে নতুন ম্যাট্রিক্স পাবো, ধরি নতুন ম্যাট্রিক্সটি A' .
তাহলে A' এর ডাইমেনশন হবেঃ A' [ 10 x 5 ]; [ P x R ]
এখন, ( A' * C ) এর জন্য cost, c2 = 10 * 5 * 50 = 2500
সুতরাং, টোটাল cost, c = 5000 + 2500 = 7500

একইভাবে A * ( B * C ) এর জন্য টোটাল cost হবে 75000
কাজেই আমাদের জন্য প্রথম অর্ডার এ মালটিপ্লাই করলে cost মিনিমাম হবে।

অ্যালগরিদম (Algorithm)

আমরা আমাদের MCM (Matrix Chain Multiplication) বের করার জন্য যে ম্যাট্রিক্সগুলি দেয়া থাকবে, সেগুলি থেকে আমরা তাদের ডাইমেনশনকে একটু মডিফাই করে একটি অ্যারেতে সেভ রাখবো এমন ভাবে যাতে, প্রতিটির ইনডেক্স এ তাদের সারির (row) মানগুলি থাকবে। উদাহরন দিলে ব্যাপারটি পরিষ্কার হবে।
ধরি, আমাদের ৬ টি ম্যাট্রিক্স দেয়া আছে এভাবেঃ

A1 [ 30 x 35 ]

A2 [ 35 x 15 ]

A3 [ 15 x 5 ]

A4 [ 5 x 10 ]

A5 [ 10 x 20 ]

A6 [ 20 x 25 ]

এখন আমরা এদের সারি-কলামের মানগুলোকে একটি অ্যারে p তে এভাবে সাজায়ে রাখবোঃ

কাজেই আমরা যদি, A1 * A2 করতে চাই, তাহলে p অ্যারে থেকে আমরা p[0]*p[1]*p[2] করলেই মান পেয়ে যাবো।
তাহলে আমরা এখন একটি ফর্মুলা দাঁড়া করাতে পারি এভাবেঃ

m[i,j] = i হতে j পর্যন্ত ম্যাট্রিক্স গুন করতে মিনিমাম মালটিপ্লিকেশন।
তাহলে আমরা লিখতে পারিঃ

m[ i,j ] = { 0 if , i == j, else
                min { m[ i,k ] + m[ k+1,j ] + p[ k-1 ] * p[ k ] * p[ j ]  }; [k = 1 to j-1]

আমরা এই ফর্মুলা অনুযায়ী আমাদের MCM table জেনারেট করবো।

টেবিল জেনারেট (MCM table generate)

যেহেতু আমাদের ৬ টি ম্যাট্রিক্স, তাই আমরা 6 x 6 সাইজ এর একটি ২-ডি অ্যারে নিবো। এখন আমরা প্রতিবার, length 1 to 6 পর্যন্ত ম্যাট্রিক্স মালটিপ্লিকেশন এর অর্ডার বের করবো।
length = 1 হলে, m[i,j] = m[i,i] = m[j,j] = 0; m[i,j] হল, m ২-ডি অ্যারের i,j ইনডেক্স।

তাহলে, আমাদের টেবিল দেখতে এরকম হবে। এখানে আমরা cost গুলিকে হিসাব করবো।

length = 2 হলে,
m[1,2] = m[1,1] + m[2,2] + p[0]*p[1]*p[2] = 0+0+30*35*15 = 15750
m[2,3] = m[2,2] + m[3,3] + p[1]*p[2]*p[3] = 0+0+35*15*5 = 2625
m[3,4] = m[3,3] + m[4,4] + p[2]*p[3]*p[4] = 0+0+15*5*10 = 750

m[4.5] = m[4,4] + m[5,5] + p[3]*p[4]*p[5] = 0+0+5*10*20 = 1000

m[5,6] = m[5,5] + m[6,6] + p[4]*p[5]*p[6] = 0+0+10*20*25 = 5000

length = 3;
m[1,3] = m[1,1] + m[2,3] + p[0]*p[1]*p[3] = 0+2625+30*35*5 = 7875; k = 1
               m[1,2] + m[3,3] + p[0]*p[2]*p[3] = 15750+0+30*15*5 = 18000; k = 2
এখানে, ৩ দৈর্ঘ্যের জন্য, একবার (A1*A2)*A3, আরেকবার A1*(A2*A3) হিসাবে করে এদের মাঝে মিনিমামটি নিতে হবে। কাজেই m[1,3] = min (7875,18000) = 7875.
lenght = 3 এর জন্য আমরা k এর মান 1,2 ধরবো। এখন এভাবে length = 3 এর জন্য সকল ভ্যালু বসালে আমরা পাবোঃ

এখন length = 4 এর জন্য, k = 1,2,3 ধরে হবেঃ
m[1,4] = m[1,1] + m[2,4] + p[0]*p[1]*p[4] = 14875; k = 1
               m[1,2] + m[3,4] + p[0]*p[2]*p[4] = 21000; k = 2
               m[1,3] + m[4,4] + p[0]*p[3]*p[4] = 9375; k = 3
m[1,4] = min (14875,21000,9375) = 9375

এভাবে বাকি মান বসালে আমরা পাইঃ

length = 5;
m[1,5] = m[1,1] + m[2,5] + p[0]*p[1]*p[5] = 28125

               m[1,2] + m[3,5] + p[0]*p[2]*p[5] = 27250 

               m[1,3] + m[4,5] + p[0]*p[3]*p[5] = 11875; k = 3

               m[1,4] + m[5,5] + p[0]*p[4]*p[5] = 15375
m[1,5] = 11875, so-->

lenght = 6 -->

অর্থাৎ আমাদের ম্যাট্রিক্স মালটিপ্লিকেশন এর জন্য মিনিমাম cost = 15125. এখন আমরা যদি অর্ডার বের করতে চাই, যে কিভাবে আসলে আমরা মাল্টিপ্লিকেশনটি করলাম, এজন্য আমাদের আরো একটি 6x6 সাইজ এর অ্যারে লাগবে। এখানে আমরা প্রতিবার k এর কোন মানের জন্য মিনিমাম ভ্যালুটি নিচ্ছি, সেই k এর মান সেভ করে রাখবো।
যেমন আমরা length = 2 এর সময়, k = 1,2,3,4,5 পর্যন্ত নিয়েছিলাম। সেই অনুযায়ী মিনিমাম সাজালেঃ

আমরা এই অ্যারের নাম দিলাম s, এখানে আমরা k - partition এর নাম্বারগুলি সেভ রাখবো।
length = 3 এর জন্য, আমরা m[1,3] তে যেই মিনিমাম ভ্যালু রেখেছিলাম, সেটি ছিল k = 1 এর ভ্যালু। আমরা এরকম কিছু একটি পেয়েছিলাম-->

m[1,3] = m[1,1] + m[2,3] + p[0]*p[1]*p[3] = 0+2625+30*35*5 = 7875; k = 1
               m[1,2] + m[3,3] + p[0]*p[2]*p[3] = 15750+0+30*15*5 = 18000; k = 2

এখানে মিনিমাম ভ্যালু এর জন্য k = 1, কাজেই আমরা s[1,3] = 1 রাখবো। এভাবে length = 3,4,5,6 এর জন্য সাজালে আমাদের বাকি ঘরগুলি সাজায়ে আমরা ফাইনালি এরকম একটি ম্যাট্রিক্স পাবোঃ

অর্ডার প্রিন্ট (Order print)

আমরা এখন আমাদের ম্যাট্রিক্স এর মাল্টিপ্লিকেশন এর অর্ডারটি প্রিন্ট করবো। আমাদের অর্ডার ফাইন্ডিং এর অ্যালগরিদম ঃ

এভাবে আমরা পাবোঃ ( (A1) (A2 A3) ) ( (A4 A5) (A6) )
অর্থাৎ, এই অর্ডারে মাল্টিপ্লিকেশন চালালে আমরা মিনিমাম cost, এক্ষেত্রে 15215 পাবো।
MCM code:

প্র্যাকটিস প্রব্লেম (Practice Problems)

• Uva 348: Optimal Array Multiplication Sequence
• Poj 2246: Matrix Chain Multiplication