Showing posts with label combinatorics. Show all posts
Showing posts with label combinatorics. Show all posts

Sunday, February 18, 2018

কম্বিনেশন ( Combination )

কোন বড় গ্রুপ থেকে কিছু সংখ্যক জিনিস নিয়ে ছোট ছোট গ্রুপে ভাগ করাই হল কম্বিনেশন। এখানে পারমুটেশন এর মত অর্ডার এর কোন প্রভাব থাকেনা। যেমনঃ ৩ টি জিনিস থেকে আমরা ২ টি জিনিস নিতে পারি এভাবেঃ
(১, ২), (১,৩), (২,৩) = মোট ৩ ভাবে, এটিই কম্বিনেশন।

অর্থাৎ, n টি জিনিস থেকে r টি জিনিস কতভাবে নিতে পারি সেটিই হল n,k এর কম্বিনেশন। (এখানে k<=n)


বাইনোমিয়াল কো-এফিশিয়েন্ট ( Binomial Coefficient )

বাইনোমিয়াল কোএফিশিয়েন্ট হল অর্ডার বিবেচনা না করে ভিন্ন ভিন্ন সম্ভাবনাকে নেয়া। শুনতে কঠিন লাগলেও ব্যাপারটি আসলে কিছুইনা। আমরা n জিনিস থেকে k জিনিস নিবো, অর্ডার বিবেচনা না করে। এটিকে কতভাবে নেয়া যাবে, এটিই বাইনোমিয়াল কোএফিশিয়েন্ট, অর্থাৎ কম্বিনেশন। 
আমরা কিছু সিরিজ এর এক্সপানশন দেখিঃ

(x + y)0 = 1
(x + y)1 = x + y
(x + y)2 = x2 + 2xy + y2
(x + y)3 = x3 + 3x2y + 3xy2 + y3
(x + y)4 = x4 + 4x3y + 6x2y2 + 4xy3 + y4

এসব সিরিজ কে আমরা এভাবে লিখতে পারি কমন ফর্মেঃ 


আমরা কম্বিনেশন এর জন্য বাইনোমিয়াল কোএফিশিয়েন্ট ব্যবহার করবো, তবে তাকে মনোমিয়াল ফর্মে নিয়ে।
( মনোমিয়াল or monomial হল এমন পলিনোমিয়াল যার শুধুমাত্র একটি টার্ম আছে )। কাজেই আমাদের বাইনোমিয়াল এর রূপ হবে এরকমঃ (1 + x) n
আমরা এই ফর্মকে এক্সপানশন করলে প্রতি পাওয়ার অনুসারে প্রতি টার্ম এর একটি করে কো-এফিশিয়েন্ট পাবো। আমাদের কাজ হবে ঐ কো-এফিশিয়েন্ট নিয়ে কাজ করা। যেমন আমরা কিছু কো-এফিশিয়েন্ট দেখিঃ


আমরা n = 4 নিয়ে দেখিঃ
(1 + x)4 = x4 + 4x3 + 6x2 + 4x + 1
এখন কো-এফিশিয়েন্টগুলি হবেঃ 1  4  6  4  1
এভাবে পাওয়ার অনুযায়ী এক্সপানশন করতে থাকলে আমরা একটি সুন্দর ত্রিভুজ এর মত ডিজাইন পাই, এটি সবার প্রথম খেয়াল করেছেন প্যাসকেল (Pascal). এজন্য একে প্যাসকেলের ত্রিভুজ বলা হয়। প্যাসকেল এর শর্তানুযায়ী আমরা কম্বিনেশন এভাবে দেখতে পারিঃ

(x + y)n = (nC0)(xny0) + (nC1)(xn-11y1) + (nC2)(xn-22y2) + ... + (nCn)(x0yn);  [nCk = combnation of k element from n or n choose k]

আমরা যেহেতু বুঝতে পারলাম বাইনোমিয়াল কো-এফিশিয়েন্ট আসলে কি জিনিস, এখন আমরা কিছু অ্যালগরিদম দেখবো কিভাবে এই বাইনোমিয়াল বের করা যায়ঃ


১। ফ্যাক্টরিয়াল ( Factorial )

আমরা সরাসরি nCk ফর্মুলা ব্যবহার করে nCk বের করতে পারি।
ফর্মুলাঃ nCk  =  [ n! ] / [  k! * (n-k)! ]


কিন্তু এভাবে আমরা সর্বোচ্চ ২১-২২ ফ্যাক্টরিয়াল পর্যন্ত হিসাবে করতে পারবো। এর চেয়ে বেশি আমরা সি++ এ করতে গেলে আমাদের বিগ-ইন্টিজার লাইব্রেরি ব্যবহার করতে হবে। তবে পাইথন এ আমরা হিসাব করতে পারবো এবং এই হিসাবের কমপ্লেক্সিটি হল O(n).
আমরা বড় বড় কম্বিনেশন এর জন্য, nCk mod m এরকম কিছু একটা করে রেজাল্ট একটি নির্দিষ্ট লিমিটের মাঝে রাখতে পারি।


২। রিকার্সন ( Recursion )

nCk বের করার রিকার্সন ফর্মুলা হলঃ nCk (i,k) = nCk (i-1,k-1) + nCk (i-1,k);
আমাদের টাইম এবং স্পেস কমপ্লেক্সিটি হবেঃ O(n*k) for nCk

আমরা একে একটু মডিফাই করে স্পেস কমপ্লেক্সিটি কমিয়ে আনতে পারি। আমরা আগের সারি চেক করবো, কারন আমাদের ঐ সারিগুলো আসলে দরকার হবেনা পরে আর।


৩। কম্বিনেশন এর বিস্তার ( Expansion of Combination )

আমরা জানি, nCk  =  [ n! ] / [  k! * (n-k)! ], অর্থাৎ

               [ n(n-1)(n-2) ... (n-k+1) ] [ (n-k) ... (1) ]
-------------------------------------------------------------------------
                  [ (n-k) ... (1) ] [ k(k-1)(k-2) .... (1) ]

আমরা লব এবং হর থেকে [ (n-k) ... (1) ] টার্ম কেটে ফেলতে পারি, তাহলে আমাদের ফাইনাল টার্ম হবেঃ

 n       (n-1)      (n-2)      (n-k+1)
---  *  ------  *  ------  *  ----------
 k       (k-1)      (k-2)          (1)

আমরা একে এভাবে লিখতে পারিঃ

nCk (n,k) = 1                                             ; if k == 0
                     else  (n/k) * nCk (n-1, k-1)


৪। প্রাইম এর পাওয়ার ( Power of Prime )

আমরা ফ্যাক্টরিয়াল এর কোন প্রাইম এর পাওয়ার বের করতে পারি এভাবেঃ

Pprime = floor[ n/prime ] + floor[ n/prime2 ] + .....

এখানে n = factorial, prime = the prime whose power in n-factorial we are calculating
আমরা nCk এর মাঝে p প্রাইম এর পাওয়ার বের করবো এভাবেঃ
power = fact(n, p) - fact(r, p) - fact(n-r, p)
এরপরে আমরা ppower করবো সকল প্রাইম, p এর জন্য যারা n থেকে ছোট।


৫। চাইনিজ রিমেইন্ডার থিওরেম  ( Chinese Remainder Theorem )

যদি আমাদের এরকম বের করতে বলা হয়ঃ nCk mod m where m is not prime , সেক্ষেত্রে আমরা m কে প্রাইম এ ফ্যাক্টরাইজ করার পরে CRT(Chinese Remainder Theorem) ব্যবহার করে মান বের করবো।



Friday, January 19, 2018

Lexicographic rank of a string(without duplicate character)

লেক্সিকোগ্রাফিক বলতে বুঝায় অ্যালফাবেটিকাল অর্ডার। যেমনঃ কোন স্ট্রিং "xyz" হলে, আমরা বলতে পারি এই স্ট্রিং এর লেক্সিকোগ্রাফিক অর্ডারের প্রথমে আছে "xyz", এরপরে "xzy" .. অর্থাৎ স্ট্রিং এর সকল পারমুটেশন এর সিরিয়াল, যারা কিনা ছোট থেকে বড় আকারে সর্টেড অবস্থায় আছে। এখন এরকম একটি স্ট্রিং দেখে আমাদের বলতে হবে এর র‍্যাঙ্ক কত। যেমনঃ "abc" এর ক্ষেত্রে, rank of "abc" = 1, rank of "acb" = 2 .... এভাবে।
একদম ব্যাসিকভাবে চিন্তা করলে আমরা সকল পারমুটেশন জেনারেট করে দেখতে পারি যে স্ট্রিং টি কততম পারমুটেশন এর সাথে মিলে গেছে। তাহলে সেটিই আমাদের স্ট্রিং এর র‍্যাঙ্ক।



এভাবে আমাদের টাইম কমপ্লেক্সিটি অনেক বেড়ে যাবে, প্রায় এক্সপোনেন্ট হারে!! (exponent) এজন্য আমাদের আরো ভালো এপ্রোচ দরকার।
আমরা একটি স্ট্রিং ধরি, "FRIEND" এর র‍্যাঙ্ক বের করতে হবে। এখানে প্রথম ক্যারেক্টার  "F" এবং "F" এর চেয়ে ছোট ২ টি ক্যারেক্টার আছে ("D", "E") এবং "F" কে তার জায়গায় ফিক্সড করলে আমাদের বাকি থাকে আরো ৫ টি জায়গা এবং "F" এর আগের ২ টি ক্যারেক্টার ঐ ৫ টি জায়গায় বসতে পারবে ৫ ফ্যাক্টরিয়াল (5!) উপায়ে। তাহলে ২ টির জন্য কম্বিনেশন হবে ২*৫!
এখন আমরা তাহলে "F" এর কাজ শেষ হলে, "F" কে ফিক্সড করে দেই। মানে "F" নিয়ে আমাদের আর মাথা ব্যথা করতে হবে না। এখন দ্বিতীয় ক্যারেক্টার "R" নিয়ে দেখি। "R" এর চেয়ে ছোট ৪ টি ক্যারেক্টার আছে ("D", "E", "I", "N"). ["F" কে আমরা ফিক্সড করে দিয়েছি, কাজেই "F" বাদ] 
তাহলে আমরা "R" এর জন্য পাবোঃ ২*৫! + ৪*৪! (আগের "F" এরগুলোও ধরতে হবে)।
একই ভাবে আমরা বাকি ক্যারেক্টার গুলোর জন্য করে ফেলিঃ

"I" = 2*5! + 4*4! + 2*3!
"E" = 2*5! + 4*4! + 2*3! + 1*2!
"N" = 2*5! + 4*4! + 2*3! + 1*2! + 1*1!
"D" = 2*5! + 4*4! + 2*3! + 1*2! + 1*1! +
0*0!
তাহলে, "FRIEND" এর জন্য র‍্যাঙ্ক হবে ঃ 2*5! + 4*4! + 2*3! + 1*2! + 1*1! + 0*0! = 351
যেহেতু, র‍্যাঙ্ক ১ থেকে শুরু হয়, কাজেই আমাদের ফাইনাল রেজাল্ট হবে 1 + 351 = 352.



এর কপ্লেক্সিটি O(n2)। আমরা একটু বুদ্ধি খাটালে এর কমপ্লেক্সিটিকে কমিয়ে আনতে পারবো। এজন্য আমরা কিউমুলেটিভ ভাবে প্রতিটি ক্যারেক্টারের চেয়ে ছোট ক্যারেক্টারকে একটি অ্যারেতে সেভ করে রাখবো।এরপরে প্রতিবার সেখান থেকে কাউন্ট নিয়ে আমরা কাজ করবো O(n) কপ্লেক্সিটিতে