বিন্যাস প্যাটার্ন

গুচ্ছ-বিন্যাসতত্ত্ব এবং তাত্ত্বিক কম্পিউটার বিজ্ঞানে, একটি বিন্যাস প্যাটার্ন হল একটি দীর্ঘ স্থানান্তরের একটি সাব-পারমুটেশন। যেকোনো স্থানচ্যুতি এক-লাইনের স্বরলিপিতে লেখা হতে পারে অঙ্কের ক্রম ১২৩... নম্বরে স্থানান্তর প্রয়োগের ফলাফলকে প্রতিনিধিত্ব করে। উদাহরণস্বরূপ, অঙ্কের ক্রম ২১৩ তিনটি উপাদানের স্থানান্তরকে উপস্থাপন করে যা উপাদান ১ এবং ২ কে অদলবদল করে। যদি π এবং σ এইভাবে দুটি ক্রমবিন্যাস প্রতিনিধিত্ব করে (এই পরিবর্তনশীল নামগুলি ক্রমপরিবর্তনের জন্য মানক এবং সংখ্যা পাই-এর সাথে সম্পর্কিত নয়), তবে বলা হয় π একটি "প্যাটার্ন" হিসাবে σ "ধারণ করে" যদি π সংখ্যার কিছু উপক্রমের σ সমস্ত সংখ্যার মতো একই আপেক্ষিক ক্রম থাকে।
উদাহরণস্বরূপ, ক্রমাগত π-এ প্যাটার্ন ২১৩ থাকে যখনই π-এ তিনটি সংখ্যা থাকে "x", "y", এবং "z" যা π-এর মধ্যে "x...y...z" ক্রমে প্রদর্শিত হয় কিন্তু যার মানগুলি "y হিসাবে সাজানো হয়" "y" < "x" < "z", ক্রমাগত ২১৩-এ মানগুলির ক্রমানুসারে একই। পাঁচটি উপাদানের পরম্যুটেশন ৩২৪১৫-এ প্যাটার্ন হিসাবে ২১৩টি বিভিন্ন উপায়ে রয়েছে: ৩··১৫, ··৪১৫, ৩২··৫, ৩২৪··, এবং ·২·১৫ সবগুলো সংখ্যার ত্রিগুণ গঠন করে যার ক্রম ২১৩-এর মতো। পরবর্তী ৩১৫, ৪১৫, ৩২৫, ৩২৪ এবং ২১৫ এর প্রতিটিকে প্যাটার্নের একটি "অনুলিপি," "উদাহরণ" বা "ঘটনা" বলা হয়। সত্য যে π-এ σ রয়েছে তা আরও সংক্ষিপ্তভাবে σ ≤ π হিসাবে লেখা হয়েছে। যদি একটি স্থানান্তর π-এ একটি প্যাটার্ন σ না থাকে, তাহলে π-কে σ "এড়াতে" বলা হয়। পারমুটেশন ৫১৩৪২ ২১৩কে এড়িয়ে যায়; এটিতে তিনটি সংখ্যার ১০টি অনুগামী আছে, কিন্তু এই ১০টি অনুসারীর কোনটিরই ২১৩টির মতো একই ক্রম নেই।
একটি মামলা করা যেতে পারে যে তিনিই প্রথম "ল্যাটিস পারমুটেশন" নিয়ে গবেষণার মাধ্যমে এই ক্ষেত্রে ফলাফল প্রমাণ করেন। বিশেষ করে ম্যাকমোহন দেখায় যে ক্রমিউটেশনগুলিকে দুটি ক্রমহ্রাসমান পরবর্তীকালে ভাগ করা যায় (অর্থাৎ, 123-এড়িয়ে যাওয়া পারমিউটেশনগুলি) কাতালান সংখ্যা দ্বারা গণনা করা হয়।
ক্ষেত্রের আরেকটি প্রাথমিক ল্যান্ডমার্ক ফলাফল হল Erdős–Szekeres উপপাদ্য ; পারমুটেশন প্যাটার্নের ভাষায়, উপপাদ্যটি বলে যে কোনো ধনাত্মক পূর্ণসংখ্যা "a" এবং "b এর" জন্য দৈর্ঘ্যের প্রতিটি স্থানান্তর formula_1 প্যাটার্ন অবশ্যই থাকতে হবে formula_2 বা প্যাটার্ন formula_3 .
বিন্যাস রীতির এই গবেষণার সঙ্গে আংশিক আন্তরিক শুরু ডোনাল্ড Knuth এর 'র বিবেচনা স্ট্যাক-বাছাই 1968 সালে নুথ দেখিয়েছেন যে π 231 এড়িয়ে গেলে এবং শুধুমাত্র যদি π একটি স্ট্যাকের দ্বারা বাছাই করা যায় এবং স্ট্যাক-সর্টেবল পারমুটেশনগুলি কাতালান সংখ্যা দ্বারা গণনা করা হয়। নুথ ডিক দিয়ে সাজানোর বিষয়েও প্রশ্ন তুলেছেন। বিশেষ করে, নুথের প্রশ্ন জিজ্ঞাসা করে যে "একটি ডিক ব্যবহার করে n" উপাদানের কতগুলি স্থানান্তর পাওয়া যায় তা খোলা থাকে। কিছুক্ষণ পরে, স্ট্যাকের নেটওয়ার্ক দ্বারা বাছাই করা তদন্ত করেছে, যখন দেখিয়েছেন যে ক্রমাগত π একটি deque দ্বারা বাছাই করা যেতে পারে যদি এবং শুধুমাত্র যদি সমস্ত "k এর জন্য", π এড়িয়ে যায় 5,2,7,4...,4 "k" +1,4 "k" − 2,3,4 "k", 1, এবং 5,2,7,4...,4 "k" +3,4 "k", 1,4 "k" +2,3, এবং প্রতিটি স্থানান্তর যা শেষ দুটি উপাদান বিনিময় করে এই দুটির যে কোনো একটি থেকে পাওয়া যেতে পারে অথবা 1 এবং 2। কারণ এই পারমুটেশনের সংগ্রহটি অসীম (আসলে, এটি একটি অসীম অ্যান্টিচেইন অফ পারমুটেশনের প্রথম প্রকাশিত উদাহরণ), এটি অবিলম্বে স্পষ্ট নয় যে একটি স্থানান্তরকে একটি ডিক দ্বারা বাছাই করা যায় কিনা তা সিদ্ধান্ত নিতে কতক্ষণ সময় লাগে। পরে একটি রৈখিক (π এর দৈর্ঘ্যে) সময় অ্যালগরিদম উপস্থাপন করেন যা নির্ধারণ করে যে π কে একটি deque দ্বারা সাজানো যায় কিনা।
তার গবেষণাপত্রে, প্র্যাট মন্তব্য করেছেন যে এই স্থানচ্যুতি প্যাটার্ন আদেশ "সরল এবং প্রাকৃতিক উপায়ে উত্থাপিত স্থানচ্যুতিতে একমাত্র আংশিক ক্রম বলে মনে হচ্ছে" এবং "একটি বিমূর্ত দৃষ্টিকোণ থেকে", স্থানান্তর প্যাটার্ন অর্ডারটি "হয়" আমরা যে নেটওয়ার্কগুলিকে চিহ্নিত করছি তার চেয়েও বেশি আকর্ষণীয়”।
স্থানচ্যুতি প্যাটার্নগুলির অধ্যয়নের একটি বিশিষ্ট লক্ষ্য হল একটি নির্দিষ্ট (এবং সাধারণত সংক্ষিপ্ত) স্থানচ্যুতি বা পারমিউটেশনের সেট এড়াতে পারমিউটেশনের গণনা করা। "Av " "(B) দৈর্ঘ্যের n-" এর পারমুটেশনের সেটকে বোঝাতে দিন "যা B" সেটের সমস্ত পারমুটেশন এড়িয়ে যায় (যে ক্ষেত্রে "B" একটি সিঙ্গলটন, বলুন β, এর পরিবর্তে সংক্ষেপণ "Av " (β) ব্যবহার করা হয়)। উপরে উল্লিখিত হিসাবে, ম্যাকমোহন এবং নুথ দেখিয়েছেন যে | "Av " (123)| = | "Av " (231)| = "C ", "n" তম কাতালান সংখ্যা। এইভাবে এগুলি হল আইসোমরফিক কম্বিনেটরিয়াল ক্লাস ।
সাধারণভাবে, যদি | "Av " (β)| = | "Av " (σ)| সকলের জন্য "n", তারপর β এবং σ কে <nowiki>Wilf-সমতুল্য বলা হয়</nowiki> । অনেক Wilf-সমতা তুচ্ছ সত্য যে | "Av " (β)| = | "Av " ( "β" )| = | "Av " (β )| সকলের জন্য "n", যেখানে β বোঝায় β এর বিপরীত এবং β বোঝায় β এর বিপরীত। (এই দুটি ক্রিয়াকলাপ ডিহেড্রাল গ্রুপ ডি <nowiki></nowiki> তৈরি করে যা পারমুটেশন ম্যাট্রিক্সের উপর একটি প্রাকৃতিক ক্রিয়া করে। ) যাইহোক, ননট্রিভিয়াল উইল্ফ-ইকুইভালেন্সের অসংখ্য উদাহরণ রয়েছে (যেমন "123" এবং "231 এর মধ্যে" ):
এই দুটি উইল্ফ-সমান এবং বিপরীত এবং বিপরীত প্রতিসাম্য থেকে, এটি অনুসরণ করে যে তিনটি ভিন্ন ক্রম রয়েছে | "Av " (β)| যেখানে β দৈর্ঘ্য চার:
1980 এর দশকের শেষের দিকে, রিচার্ড স্ট্যানলি এবং হার্বার্ট উইল্ফ অনুমান করেছিলেন যে প্রতিটি স্থানচ্যুতি β-এর জন্য কিছু ধ্রুবক "K থাকে" যেটা | "Av " (β)| < "কে " । অ্যাডাম মার্কাস এবং গাবর টারডোস দ্বারা প্রমাণিত না হওয়া পর্যন্ত এটি স্ট্যানলি-উইল্ফ অনুমান হিসাবে পরিচিত ছিল। 
"রুদ্ধ বর্গ," একটি "প্যাটার্ন বর্গ," "বিন্যাস বর্গ," বা শুধু একাধিক বিন্যাসন "বর্গ" নামে পরিচিত হয় downset বিন্যাস প্যাটার্ন যাতে। প্রতিটি শ্রেণীকে সংজ্ঞায়িত করা যেতে পারে ন্যূনতম পারমুটেশন দ্বারা যা এর ভিতরে থাকে না, এর "ভিত্তি" । এইভাবে স্ট্যাক-সর্টেবল পারমিউটেশনের ভিত্তি হল {231}, যখন ডিক-সর্টেবল পারমিউটেশনের ভিত্তি অসীম। একটি ক্লাসের জন্য "তৈরি ফাংশন" যেখানে যোগফল শ্রেণীতে সমস্ত স্থানান্তর π ধরে নেওয়া হয়।
যেহেতু কন্টেনমেন্ট অর্ডারের অধীনে পারমুটেশনের সেটটি একটি পোজেট গঠন করে তাই এর Möbius ফাংশন সম্পর্কে জিজ্ঞাসা করা স্বাভাবিক, একটি লক্ষ্য প্রথম স্পষ্টভাবে দ্বারা উপস্থাপিত। এই ধরনের তদন্তের লক্ষ্য হল একটি ব্যবধান [σ, π]-এর Möbius ফাংশনের জন্য একটি সূত্র খুঁজে বের করা যা পারমুটেশন প্যাটার্ন পোজেটে ন্যাভ রিকারসিভ সংজ্ঞার চেয়ে বেশি কার্যকর। এই ধরনের প্রথম ফলাফল দ্বারা প্রতিষ্ঠিত হয়েছিল, যিনি স্তরবিন্যাসগুলির একটি ব্যবধানের Möbius ফাংশনের জন্য একটি সূত্র দিয়েছিলেন। পরে, এই ফলাফলটিকে বিভাজ্য স্থানচ্যুতির ব্যবধানে সাধারণীকরণ করেছে। 
এটা জানা যায় যে, লক্ষণীয়ভাবে, অন্তত 39.95% সমস্ত পারমিউটেশনের π দৈর্ঘ্য "n" সন্তুষ্ট করে μ(1, π)=0 (অর্থাৎ, প্রধান Möbius ফাংশনটি শূন্যের সমান), কিন্তু প্রতিটি "n-এর" জন্য বিদ্যমান পারমিউটেশন π যেমন μ(1, π) হল "n এর" একটি সূচকীয় ফাংশন। 
একটি স্থানান্তর দেওয়া formula_4 "(টেক্সট" বলা হয়) দৈর্ঘ্যের formula_5 এবং আরেকটি স্থানান্তর formula_6 দৈর্ঘ্যের formula_7 "(প্যাটার্ন" বলা হয় ), "পারমুটেশন প্যাটার্ন ম্যাচিং (PPM)" সমস্যা জিজ্ঞাসা করে কিনা formula_6 এর মধ্যে রয়েছে formula_4 . যখন উভয় formula_5 এবং formula_7 ভেরিয়েবল হিসাবে গণ্য করা হয়, সমস্যাটি NP-সম্পূর্ণ বলে পরিচিত, এবং এই ধরনের ম্যাচের সংখ্যা গণনার সমস্যা হল #P-complete । যাইহোক, PPM রৈখিক সময়ে সমাধান করা যেতে পারে যখন "k" একটি ধ্রুবক হয়। প্রকৃতপক্ষে, গুইলেমোট এবং মার্কস দেখিয়েছেন যে পিপিএম সময়মতো সমাধান করা যেতে পারে formula_12, এর মানে হল যে এটি ফিক্সড-প্যারামিটার ট্র্যাক্টেবল formula_7 .
ব্রুনার এবং ল্যাকনার দ্বারা জরিপ করা হিসাবে PPM সমস্যার বিভিন্ন রূপ রয়েছে। উদাহরণস্বরূপ, যদি মিলটি সংলগ্ন এন্ট্রিগুলির সমন্বয়ে প্রয়োজন হয় তবে সমস্যাটি বহুপদী সময়ে সমাধান করা যেতে পারে। 
আরেকটি বৈকল্পিক হল যখন প্যাটার্ন এবং টেক্সট উভয়ই একটি সঠিক পারমুটেশন ক্লাসে সীমাবদ্ধ থাকে formula_14, যে ক্ষেত্রে সমস্যা বলা হয় formula_14 -পিপিএম। উদাহরণস্বরূপ, গুইলেমোট এবং ভায়ালেট দেখিয়েছেন formula_16 -পিপিএম এর মধ্যে সমাধান করা যেতে পারে formula_17 সময় আলবার্ট, ল্যাকনার, ল্যাকনার এবং ভ্যাটার পরে এটিকে নামিয়ে আনেন formula_18 এবং দেখিয়েছে যে তির্যক-মার্জিত পারমুটেশনের ক্লাসের জন্য একই আবদ্ধ রয়েছে। তারা আরও জানতে চাইলেন যে formula_14 -পিপিএম সমস্যা প্রতিটি নির্দিষ্ট সঠিক স্থানান্তর শ্রেণীর জন্য বহুপদী সময়ে সমাধান করা যেতে পারে formula_14 .
ক্রমিউটেশন π কে β- "সর্বোত্তম বলা হয়" যদি π এর মতো একই দৈর্ঘ্যের কোনো পারমুটেশনে β-এর বেশি কপি না থাকে। 1992 সালে বিচ্ছিন্ন গণিতের উপর সিয়াম সভায় তার ভাষণে, উইল্ফ "k" দৈর্ঘ্যের β-এর "প্যাকিং ঘনত্বকে সংজ্ঞায়িত করেছিলেন"
ফ্রেড গ্যালভিনের একটি অপ্রকাশিত যুক্তি দেখায় যে এই সীমার "ভিতরের পরিমাণ n" ≥ "k এর" জন্য বৃদ্ধি পাচ্ছে না, এবং তাই সীমাটি বিদ্যমান। যখন β একঘেয়ে হয়, তখন এর প্যাকিং ঘনত্ব স্পষ্টভাবে 1 হয়, এবং প্যাকিং ঘনত্ব বিপরীত এবং বিপরীত দ্বারা উত্পন্ন প্রতিসাম্যের গ্রুপের অধীনে অপরিবর্তনীয়, তাই দৈর্ঘ্য তিনের ক্রমিউটেশনের জন্য, শুধুমাত্র একটি ননট্রিভিয়াল প্যাকিং ঘনত্ব থাকে। ওয়াল্টার স্ট্রোমকুইস্ট (অপ্রকাশিত) 132 এর প্যাকিং ঘনত্ব 2 √ 3 দেখিয়ে এই মামলাটি নিষ্পত্তি করেছেন − 3, প্রায় 0.46410।
চারটি দৈর্ঘ্যের β পারমিউটেশনের জন্য, (প্রতিসাম্যের কারণে) সাতটি ক্ষেত্রে বিবেচনা করতে হবে:
তিনটি অজানা পরিবর্তনের জন্য, সীমা এবং অনুমান আছে। একটি আনুমানিক অ্যালগরিদম ব্যবহার করেছে যা প্রস্তাব করে যে 1324 এর প্যাকিং ঘনত্ব প্রায় 0.244। বিরজান বাটকেয়েভ (অপ্রকাশিত) একটি পারমুটেশনের পরিবার তৈরি করেছেন যাতে দেখায় যে 1342 এর প্যাকিং ঘনত্ব কমপক্ষে 132 এবং 1432 এর প্যাকিং ঘনত্বের গুণফল, প্রায় 0.19658। এটি 1342 এর সুনির্দিষ্ট প্যাকিং ঘনত্ব বলে অনুমান করা হয়। 2413 এর প্যাকিং ঘনত্বে একটি নিম্ন সীমা প্রদান করেছে। এই নিম্ন সীমা, যা একটি অবিচ্ছেদ্য পরিপ্রেক্ষিতে প্রকাশ করা যেতে পারে, আনুমানিক 0.10474, এবং এটি প্রকৃত প্যাকিং ঘনত্ব বলে অনুমান করা হয়। 
A "k" - সুপারপ্যাটার্ন হল একটি পারমুটেশন যাতে "k" দৈর্ঘ্যের সমস্ত ক্রমিউটেশন থাকে। উদাহরণস্বরূপ, 25314 হল একটি 3-সুপারপ্যাটার্ন কারণ এতে 3 দৈর্ঘ্যের সমস্ত 6টি পারমুটেশন রয়েছে। এটা জানা যায় যে "k" -superpatterns এর দৈর্ঘ্য কমপক্ষে "k" /"e" , যেখানে "e" ≈ 2.71828 হল অয়লারের সংখ্যা, এবং "দৈর্ঘ্যের k" -সুপার প্যাটার্ন "রয়েছে ⌈( k"  + 1)/2⌉। এই ঊর্ধ্ব সীমা নিম্ন-অর্ডার শর্তাবলী পর্যন্ত সর্বোত্তম সম্ভব বলে অনুমান করা হয়। 
"প্যাটার্ন" ধারণাটি সাধারণীকরণ করা হয়েছে এমন বিভিন্ন উপায় রয়েছে। উদাহরণ স্বরূপ, একটি "ভিনকুলার প্যাটার্ন" হল ড্যাশ সমন্বিত একটি পারমুটেশন যা এন্ট্রিগুলিকে নির্দেশ করে যা ধারাবাহিকভাবে ঘটতে হবে না (সাধারণ প্যাটার্নের সংজ্ঞায়, কোনো এন্ট্রি ধারাবাহিকভাবে ঘটতে হবে না)। উদাহরণস্বরূপ, পারমুটেশন 314265-এ ড্যাশড প্যাটার্ন 2-31-4 এর দুটি কপি রয়েছে, যা 3426 এবং 3425 এন্ট্রি দ্বারা দেওয়া হয়েছে। একটি ড্যাশড প্যাটার্ন β এবং যেকোনো স্থানান্তর π-এর জন্য, আমরা π-এ β-এর কপি সংখ্যার জন্য β(π) লিখি। এইভাবে π-এ বিপরীতের সংখ্যা হল 2-1(π), যখন অবতরণ সংখ্যা হল 21(π)। যাওয়া আরো π মধ্যে "উপত্যকার" সংখ্যা 213 (π) + + 312 (π), যখন "পীক" সংখ্যা 231 (π) + + 132 (π) হয়। দ্বারা প্রবর্তিত হয়েছিল, যিনি দেখিয়েছিলেন যে প্রায় সমস্ত পরিচিত মহোনিয়ান পরিসংখ্যানগুলি ভিনকুলার পারমিউটেশনের ক্ষেত্রে প্রকাশ করা যেতে পারে। উদাহরণস্বরূপ, π-এর প্রধান সূচক 1-32(π) + 2-31(π) + 3-21(π) + 21(π) এর সমান।
আরেকটি সাধারণীকরণ হল একটি "ব্যারেড প্যাটার্ন", যাতে কিছু এন্ট্রি নিষিদ্ধ করা হয়। π-এর জন্য বাধা প্যাটার্ন এড়ানোর জন্য β মানে হল π-এর প্রতিটি এন্ট্রির সেট যা β-এর অ-বারিত এন্ট্রিগুলির একটি অনুলিপি তৈরি করে β-এর সমস্ত এন্ট্রিগুলির একটি অনুলিপি তৈরি করতে প্রসারিত করা যেতে পারে। তার পারমুটেশনের গবেষণায় এই ধরনের নিদর্শনগুলি প্রবর্তন করেছিলেন যা একটি স্ট্যাকের মধ্য দিয়ে দুবার পাস করে সাজানো যেতে পারে। (উল্লেখ্য যে একটি স্ট্যাকের মাধ্যমে দুইবার সাজানোর ওয়েস্টের সংজ্ঞাটি সিরিজে দুটি স্ট্যাকের সাথে সাজানোর মত নয়। ) বর্ধিত নিদর্শনগুলির আরেকটি উদাহরণ রচনায় দেখা যায়, যিনি দেখিয়েছিলেন যে π এর সাথে সম্পর্কিত Schubert জাত স্থানীয়ভাবে ফ্যাক্টরিয়াল যদি এবং শুধুমাত্র যদি π 1324 এবং 21 3 54 
২০০৩ সাল থেকে প্রতি বছর পারমুটেশন প্যাটার্নের উপর একটি সম্মেলন অনুষ্ঠিত হচ্ছে:
আমেরিকান ম্যাথমেটিকাল সোসাইটি নিম্নলিখিত মিটিংগুলিতে প্যাটার্নস ইন পারমুটেশনের বিশেষ অধিবেশন অনুষ্ঠিত হয়েছে:
অন্যান্য স্থানান্তর নিদর্শন মিটিং:
অন্যান্য লিঙ্ক: