math.combinatorics ভোকাবুলারি একগুচ্ছ আইটেম নিয়ে দুই ধরনের প্রশ্নের উত্তর দেয়:
-
কম্বিনেশন: ক্রমকে গুরুত্ব না দিয়ে একটি গ্রুপ বেছে নেওয়ার কতগুলো উপায় আছে, কিংবা কোন কোন উপায়ে বেছে নেওয়া যায়?
-
পারমিউটেশন: যেখানে ক্রম গুরুত্বপূর্ণ, সেখানে আইটেম সাজানোর কতগুলো উপায় আছে, বা কোন কোন উপায়ে সাজানো যায়?
প্রতিটি প্রশ্নের জন্য একটি গণনা-ধরনের শব্দ থাকে যা একটি সংখ্যা রিটার্ন করে, আর একটি তালিকা-ধরনের শব্দ থাকে যা সত্যিকার নির্বাচনগুলো রিটার্ন করে।
গণনা
nCk ("n choose k") রিটার্ন করে n সংখ্যক আইটেম থেকে k-এলিমেন্টের কতগুলো কম্বিনেশন বেছে নেওয়া যায়:
nCk ( n k -- m )
USING: math.combinatorics prettyprint ;
5 2 nCk . ! => 10
6 3 nCk . ! => 20
5 5 nCk . ! => 1
nPk রিটার্ন করে n সংখ্যক আইটেম থেকে k-এলিমেন্টের ক্রমযুক্ত নির্বাচন (পারমিউটেশন) কতভাবে করা যায়। যেহেতু ক্রম গুরুত্বপূর্ণ, তাই এই গণনা সংশ্লিষ্ট nCk-এর চেয়ে কম হতে পারে না:
nPk ( n k -- m )
5 2 nPk . ! => 20
6 3 nPk . ! => 120
কম্বিনেশন তালিকাভুক্ত করা
all-combinations একটি সিকোয়েন্সের প্রতিটি k-এলিমেন্টের সাবসেট রিটার্ন করে। প্রতিটি কম্বিনেশনের ভেতরের এলিমেন্টগুলো তাদের আসল ক্রম অটুট রাখে, আর কম্বিনেশনগুলো লেক্সিকোগ্রাফিক ক্রমে ফিরে আসে:
all-combinations ( seq k -- combinations )
{ 1 2 3 } 2 all-combinations .
! => { { 1 2 } { 1 3 } { 2 3 } }
যখন আপনি প্রতিটি কম্বিনেশন সবগুলো একসাথে জমা না করে যেভাবে তৈরি হচ্ছে সেভাবেই প্রসেস করতে চান, তখন স্ট্রিমিং রূপ each-combination ব্যবহার করুন, যা প্রতিটি কম্বিনেশন নিয়ে একটি কোয়োটেশন কল করে:
each-combination ( seq k quot -- )
{ 1 2 3 } 2 [ . ] each-combination
! => { 1 2 }
! => { 1 3 }
! => { 2 3 }
পারমিউটেশন তালিকাভুক্ত করা
all-permutations একটি সিকোয়েন্সের সম্ভাব্য প্রতিটি ক্রম রিটার্ন করে:
all-permutations ( seq -- permutations )
{ 1 2 } all-permutations .
! => { { 1 2 } { 2 1 } }
{ 1 2 3 } all-permutations .
! => { { 1 2 3 } { 1 3 2 } { 2 1 3 } { 2 3 1 } { 3 1 2 } { 3 2 1 } }
এর স্ট্রিমিং প্রতিরূপ হলো each-permutation, যা প্রতিটি ক্রম নিয়ে একটি কোয়োটেশন কল করে:
each-permutation ( seq quot -- )
{ 1 2 } [ . ] each-permutation
! => { 1 2 }
! => { 2 1 }
লার্নিং অনুশীলনী
