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

উইকিপিডিয়া, মুক্ত বিশ্বকোষ থেকে

গুচ্ছ-বিন্যাসতত্ত্ব এবং তাত্ত্বিক কম্পিউটার বিজ্ঞানে, একটি বিন্যাস প্যাটার্ন হল একটি দীর্ঘ স্থানান্তরের একটি সাব-পারমুটেশন। যেকোনো স্থানচ্যুতি এক-লাইনের স্বরলিপিতে লেখা হতে পারে অঙ্কের ক্রম ১২৩... নম্বরে স্থানান্তর প্রয়োগের ফলাফলকে প্রতিনিধিত্ব করে। উদাহরণস্বরূপ, অঙ্কের ক্রম ২১৩ তিনটি উপাদানের স্থানান্তরকে উপস্থাপন করে যা উপাদান ১ এবং ২ কে অদলবদল করে। যদি π এবং σ এইভাবে দুটি ক্রমবিন্যাস প্রতিনিধিত্ব করে (এই পরিবর্তনশীল নামগুলি ক্রমপরিবর্তনের জন্য মানক এবং সংখ্যা পাই-এর সাথে সম্পর্কিত নয়), তবে বলা হয় π একটি প্যাটার্ন হিসাবে σ ধারণ করে যদি π সংখ্যার কিছু উপক্রমের σ সমস্ত সংখ্যার মতো একই আপেক্ষিক ক্রম থাকে। উদাহরণস্বরূপ, ক্রমাগত π-এ প্যাটার্ন ২১৩ থাকে যখনই π-এ তিনটি সংখ্যা থাকে x, y, এবং z যা π-এর মধ্যে x...y...z ক্রমে প্রদর্শিত হয় কিন্তু যার মানগুলি y হিসাবে সাজানো হয় y < x < z, ক্রমাগত ২১৩-এ মানগুলির ক্রমানুসারে একই। পাঁচটি উপাদানের পরম্যুটেশন ৩২৪১৫-এ প্যাটার্ন হিসাবে ২১৩টি বিভিন্ন উপায়ে রয়েছে: ৩··১৫, ··৪১৫, ৩২··৫, ৩২৪··, এবং ·২·১৫ সবগুলো সংখ্যার ত্রিগুণ গঠন করে যার ক্রম ২১৩-এর মতো। পরবর্তী ৩১৫, ৪১৫, ৩২৫, ৩২৪ এবং ২১৫ এর প্রতিটিকে প্যাটার্নের একটি অনুলিপি, উদাহরণ বা ঘটনা বলা হয়। সত্য যে π-এ σ রয়েছে তা আরও সংক্ষিপ্তভাবে σ ≤ π হিসাবে লেখা হয়েছে। যদি একটি স্থানান্তর π-এ একটি প্যাটার্ন σ না থাকে, তাহলে π-কে σ এড়াতে বলা হয়। পারমুটেশন ৫১৩৪২ ২১৩কে এড়িয়ে যায়; এটিতে তিনটি সংখ্যার ১০টি অনুগামী আছে, কিন্তু এই ১০টি অনুসারীর কোনটিরই ২১৩টির মতো একই ক্রম নেই।

প্রাথমিক ফলাফল[সম্পাদনা]

একটি মামলা করা যেতে পারে যে Percy MacMahon (১৯১৫) তিনিই প্রথম "ল্যাটিস পারমুটেশন" নিয়ে গবেষণার মাধ্যমে এই ক্ষেত্রে ফলাফল প্রমাণ করেন।[১] বিশেষ করে ম্যাকমোহন দেখায় যে ক্রমিউটেশনগুলিকে দুটি ক্রমহ্রাসমান পরবর্তীতে ভাগ করা যায় (অর্থাৎ, 123-এড়িয়ে যাওয়া পারমিউটেশনগুলি) কাতালান সংখ্যা দ্বারা গণনা করা হয়।[২] ক্ষেত্রের আরেকটি প্রাথমিক ল্যান্ডমার্ক ফলাফল হল Erdős–Szekeres উপপাদ্য ; পারমুটেশন প্যাটার্নের ভাষায়, উপপাদ্যটি বলে যে কোনো ধনাত্মক পূর্ণসংখ্যা a এবং b এর জন্য দৈর্ঘ্যের প্রতিটি স্থানান্তর প্যাটার্ন অবশ্যই থাকতে হবে বা প্যাটার্ন .

কম্পিউটার বিজ্ঞানের উৎপত্তি[সম্পাদনা]

বিন্যাস রীতির এই গবেষণার সঙ্গে আংশিক আন্তরিক শুরু ডোনাল্ড Knuth এর 'র বিবেচনা স্ট্যাক-বাছাই 1968 সালে[৩] নুথ দেখিয়েছেন যে π 231 এড়িয়ে গেলে এবং শুধুমাত্র যদি π একটি স্ট্যাকের দ্বারা বাছাই করা যায় এবং স্ট্যাক-সর্টেবল পারমুটেশনগুলি কাতালান সংখ্যা দ্বারা গণনা করা হয়।[৪] নুথ ডিক দিয়ে সাজানোর বিষয়েও প্রশ্ন তুলেছেন। বিশেষ করে, নুথের প্রশ্ন জিজ্ঞাসা করে যে একটি ডিক ব্যবহার করে n উপাদানের কতগুলি স্থানান্তর পাওয়া যায় তা খোলা থাকে।[৫] কিছুক্ষণ পরে, Robert Tarjan (1972) স্ট্যাকের নেটওয়ার্ক দ্বারা বাছাই করা তদন্ত করেছে,[৬] যখন Vaughan Pratt (1973) দেখিয়েছেন যে ক্রমাগত π একটি 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।[৭] কারণ এই পারমুটেশনের সংগ্রহটি অসীম (আসলে, এটি একটি অসীম অ্যান্টিচেইন অফ পারমুটেশনের প্রথম প্রকাশিত উদাহরণ), এটি অবিলম্বে স্পষ্ট নয় যে একটি স্থানান্তরকে একটি ডিক দ্বারা বাছাই করা যায় কিনা তা সিদ্ধান্ত নিতে কতক্ষণ সময় লাগে। Rosenstiehl & Tarjan (1984) পরে একটি রৈখিক (π এর দৈর্ঘ্যে) সময় অ্যালগরিদম উপস্থাপন করেন যা নির্ধারণ করে যে π কে একটি deque দ্বারা সাজানো যায় কিনা।[৮] তার গবেষণাপত্রে, প্র্যাট মন্তব্য করেছেন যে এই স্থানচ্যুতি প্যাটার্ন আদেশ "সরল এবং প্রাকৃতিক উপায়ে উত্থাপিত স্থানচ্যুতিতে একমাত্র আংশিক ক্রম বলে মনে হচ্ছে" এবং "একটি বিমূর্ত দৃষ্টিকোণ থেকে", স্থানান্তর প্যাটার্ন অর্ডারটি "হয়" আমরা যে নেটওয়ার্কগুলিকে চিহ্নিত করছি তার চেয়েও বেশি আকর্ষণীয়”।[৭]

গণনামূলক উত্স[সম্পাদনা]

স্থানচ্যুতি প্যাটার্নগুলির অধ্যয়নের একটি বিশিষ্ট লক্ষ্য হল একটি নির্দিষ্ট (এবং সাধারণত সংক্ষিপ্ত) স্থানচ্যুতি বা পারমিউটেশনের সেট এড়াতে পারমিউটেশনের গণনা করা। Av n (B) দৈর্ঘ্যের n- এর পারমুটেশনের সেটকে বোঝাতে দিন যা B সেটের সমস্ত পারমুটেশন এড়িয়ে যায় (যে ক্ষেত্রে B একটি সিঙ্গলটন, বলুন β, এর পরিবর্তে সংক্ষেপণ Av n (β) ব্যবহার করা হয়)। উপরে উল্লিখিত হিসাবে, ম্যাকমোহন এবং নুথ দেখিয়েছেন যে | Av n (123)| = | Av n (231)| = C n, n তম কাতালান সংখ্যা। এইভাবে এগুলি হল আইসোমরফিক কম্বিনেটরিয়াল ক্লাস । Simion & Schmidt (1985) ছিল প্রথম কাগজ যা শুধুমাত্র গণনায় মনোনিবেশ করেছিল। অন্যান্য ফলাফলের মধ্যে, সিমিয়ন এবং শ্মিট গণনা করা হয় এমনকি এবং অদ্ভুত ক্রমপরিবর্তন দৈর্ঘ্য তিন একটি প্যাটার্ন এড়ানো, দৈর্ঘ্য তিন দুই প্যাটার্ন এড়ানো পারমুটেশন গণনা, এবং প্রথম বিজেক্টিভ প্রমাণ যে 123- এবং 231 এড়ানো ক্রমপরিবর্তন সমসংখ্যা।[৯] তাদের কাগজ থেকে, আরও অনেক বিজেকশন দেওয়া হয়েছে, একটি জরিপের জন্য ক্লায়েসন অ্যান্ড কিতায়েভ (২০০৮) দেখুন।[১০] সাধারণভাবে, যদি | Av n (β)| = | Av n (σ)| সকলের জন্য n, তারপর β এবং σ কে <i id="mwcw">Wilf-সমতুল্য বলা হয়</i> । অনেক Wilf-সমতা তুচ্ছ সত্য যে | Av n (β)| = | Av n ( β − 1 )| = | Av nrev )| সকলের জন্য n, যেখানে β -1 বোঝায় β এর বিপরীত এবং β rev বোঝায় β এর বিপরীত। (এই দুটি ক্রিয়াকলাপ ডিহেড্রাল গ্রুপ ডি <sub id="mwhA">8</sub> তৈরি করে যা পারমুটেশন ম্যাট্রিক্সের উপর একটি প্রাকৃতিক ক্রিয়া করে। ) যাইহোক, ননট্রিভিয়াল উইল্ফ-ইকুইভালেন্সের অসংখ্য উদাহরণ রয়েছে (যেমন 123 এবং 231 এর মধ্যে ):

এই দুটি উইল্ফ-সমান এবং বিপরীত এবং বিপরীত প্রতিসাম্য থেকে, এটি অনুসরণ করে যে তিনটি ভিন্ন ক্রম রয়েছে | Av n (β)| যেখানে β দৈর্ঘ্য চার:

β ক্রম গণনা Av n (β) OEIS রেফারেন্স সঠিক গণনার রেফারেন্স
 1342  1, 2, 6, 23, 103, 512, 2740, 15485, 91245, 555662, . . . A022558 Bóna (1997)[১৪]
 1234  1, 2, 6, 23, 103, 513, 2761, 15767, 94359, 586590, . . . A005802 Gessel (1990)[১৫]
 1324  1, 2, 6, 23, 103, 513, 2762, 15793, 94776, 591950, . . . A061552 অগণিত

1980 এর দশকের শেষের দিকে, রিচার্ড স্ট্যানলি এবং হার্বার্ট উইল্ফ অনুমান করেছিলেন যে প্রতিটি স্থানচ্যুতি β-এর জন্য কিছু ধ্রুবক K থাকে যেটা | Av n (β)| < কে এন । অ্যাডাম মার্কাস এবং গাবর টারডোস দ্বারা প্রমাণিত না হওয়া পর্যন্ত এটি স্ট্যানলি-উইল্ফ অনুমান হিসাবে পরিচিত ছিল। [১৬]

বন্ধ ক্লাস[সম্পাদনা]

রুদ্ধ বর্গ, একটি প্যাটার্ন বর্গ, বিন্যাস বর্গ, বা শুধু একাধিক বিন্যাসন বর্গ নামে পরিচিত হয় downset বিন্যাস প্যাটার্ন যাতে। প্রতিটি শ্রেণীকে সংজ্ঞায়িত করা যেতে পারে ন্যূনতম পারমুটেশন দ্বারা যা এর ভিতরে থাকে না, এর ভিত্তি । এইভাবে স্ট্যাক-সর্টেবল পারমিউটেশনের ভিত্তি হল {231}, যখন ডিক-সর্টেবল পারমিউটেশনের ভিত্তি অসীম। একটি ক্লাসের জন্য তৈরি ফাংশন হল Σ x |π| যেখানে যোগফল শ্রেণীতে সমস্ত স্থানান্তর π ধরে নেওয়া হয়।

Möbius ফাংশন[সম্পাদনা]

যেহেতু কন্টেনমেন্ট অর্ডারের অধীনে পারমুটেশনের সেটটি একটি পোজেট গঠন করে তাই এর Möbius ফাংশন সম্পর্কে জিজ্ঞাসা করা স্বাভাবিক, একটি লক্ষ্য প্রথম স্পষ্টভাবে Wilf (2002) দ্বারা উপস্থাপিত। [১৭] এই ধরনের তদন্তের লক্ষ্য হল একটি ব্যবধান [σ, π]-এর Möbius ফাংশনের জন্য একটি সূত্র খুঁজে বের করা যা পারমুটেশন প্যাটার্ন পোজেটে ন্যাভ রিকারসিভ সংজ্ঞার চেয়ে বেশি কার্যকর। এই ধরনের প্রথম ফলাফল Sagan & Vatter (2006) দ্বারা প্রতিষ্ঠিত হয়েছিল, যিনি স্তরবিন্যাসগুলির একটি ব্যবধানের Möbius ফাংশনের জন্য একটি সূত্র দিয়েছিলেন। [১৮] পরে, Burstein et al. (2011) এই ফলাফলটিকে বিভাজ্য স্থানচ্যুতির ব্যবধানে সাধারণীকরণ করেছে। [১৯] এটা জানা যায় যে, লক্ষণীয়ভাবে, অন্তত 39.95% সমস্ত পারমিউটেশনের π দৈর্ঘ্য n সন্তুষ্ট করে μ(1, π)=0 (অর্থাৎ, প্রধান Möbius ফাংশনটি শূন্যের সমান), [২০] কিন্তু প্রতিটি n-এর জন্য বিদ্যমান পারমিউটেশন π যেমন μ(1, π) হল n এর একটি সূচকীয় ফাংশন। [২১]

গণনীয় জটিলতা[সম্পাদনা]

একটি স্থানান্তর দেওয়া (টেক্সট বলা হয়) দৈর্ঘ্যের এবং আরেকটি স্থানান্তর দৈর্ঘ্যের (প্যাটার্ন বলা হয় ), পারমুটেশন প্যাটার্ন ম্যাচিং (PPM) সমস্যা জিজ্ঞাসা করে কিনা এর মধ্যে রয়েছে . যখন উভয় এবং ভেরিয়েবল হিসাবে গণ্য করা হয়, সমস্যাটি NP-সম্পূর্ণ বলে পরিচিত, এবং এই ধরনের ম্যাচের সংখ্যা গণনার সমস্যা হল #P-complete । [২২] যাইহোক, PPM রৈখিক সময়ে সমাধান করা যেতে পারে যখন k একটি ধ্রুবক হয়। প্রকৃতপক্ষে, গুইলেমোট এবং মার্কস [২৩] দেখিয়েছেন যে পিপিএম সময়মতো সমাধান করা যেতে পারে , এর মানে হল যে এটি ফিক্সড-প্যারামিটার ট্র্যাক্টেবল .

ব্রুনার এবং ল্যাকনার দ্বারা জরিপ করা হিসাবে PPM সমস্যার বিভিন্ন রূপ রয়েছে। [২৪] উদাহরণস্বরূপ, যদি মিলটি সংলগ্ন এন্ট্রিগুলির সমন্বয়ে প্রয়োজন হয় তবে সমস্যাটি বহুপদী সময়ে সমাধান করা যেতে পারে। [২৫] আরেকটি বৈকল্পিক হল যখন প্যাটার্ন এবং টেক্সট উভয়ই একটি সঠিক পারমুটেশন ক্লাসে সীমাবদ্ধ থাকে , যে ক্ষেত্রে সমস্যা বলা হয় -পিপিএম। উদাহরণস্বরূপ, গুইলেমোট এবং ভায়ালেট [২৬] দেখিয়েছেন -পিপিএম এর মধ্যে সমাধান করা যেতে পারে সময় আলবার্ট, ল্যাকনার, ল্যাকনার এবং ভ্যাটার [২৭] পরে এটিকে নামিয়ে আনেন এবং দেখিয়েছে যে তির্যক-মার্জিত পারমুটেশনের ক্লাসের জন্য একই আবদ্ধ রয়েছে। তারা আরও জানতে চাইলেন যে -পিপিএম সমস্যা প্রতিটি নির্দিষ্ট সঠিক স্থানান্তর শ্রেণীর জন্য বহুপদী সময়ে সমাধান করা যেতে পারে .

প্যাকিং ঘনত্ব[সম্পাদনা]

ক্রমিউটেশন π কে β- সর্বোত্তম বলা হয় যদি π এর মতো একই দৈর্ঘ্যের কোনো পারমুটেশনে β-এর বেশি কপি না থাকে। 1992 সালে বিচ্ছিন্ন গণিতের উপর সিয়াম সভায় তার ভাষণে, উইল্ফ k দৈর্ঘ্যের β-এর প্যাকিং ঘনত্বকে সংজ্ঞায়িত করেছিলেন

ফ্রেড গ্যালভিনের একটি অপ্রকাশিত যুক্তি দেখায় যে এই সীমার ভিতরের পরিমাণ nk এর জন্য বৃদ্ধি পাচ্ছে না, এবং তাই সীমাটি বিদ্যমান। যখন β একঘেয়ে হয়, তখন এর প্যাকিং ঘনত্ব স্পষ্টভাবে 1 হয়, এবং প্যাকিং ঘনত্ব বিপরীত এবং বিপরীত দ্বারা উত্পন্ন প্রতিসাম্যের গ্রুপের অধীনে অপরিবর্তনীয়, তাই দৈর্ঘ্য তিনের ক্রমিউটেশনের জন্য, শুধুমাত্র একটি ননট্রিভিয়াল প্যাকিং ঘনত্ব থাকে। ওয়াল্টার স্ট্রোমকুইস্ট (অপ্রকাশিত) 132 এর প্যাকিং ঘনত্ব 2 √ 3 দেখিয়ে এই মামলাটি নিষ্পত্তি করেছেন − 3, প্রায় 0.46410। চারটি দৈর্ঘ্যের β পারমিউটেশনের জন্য, (প্রতিসাম্যের কারণে) সাতটি ক্ষেত্রে বিবেচনা করতে হবে:

β প্যাকিং ঘনত্ব রেফারেন্স
 1234  1 নগণ্য
 1432  x 3 − 12 x 2 + 156 x − 64 ≅ 0.42357 এর মূল Price (1997)[২৮]
 2143  ⅜ = 0.375 Price (1997)[২৮]
 1243  ⅜ = 0.375 Albert et al. (2002)[২৯]
 1324  অনুমান করা হয়েছে ≅ 0.244
 1342  অনুমান করা হয়েছে ≅ 0.19658
 2413  অনুমান করা হয়েছে ≅ 0.10474

তিনটি অজানা পরিবর্তনের জন্য, সীমা এবং অনুমান আছে। Price (1997) একটি আনুমানিক অ্যালগরিদম ব্যবহার করেছে যা প্রস্তাব করে যে 1324 এর প্যাকিং ঘনত্ব প্রায় 0.244।[২৮] বিরজান বাটকেয়েভ (অপ্রকাশিত) একটি পারমুটেশনের পরিবার তৈরি করেছেন যাতে দেখায় যে 1342 এর প্যাকিং ঘনত্ব কমপক্ষে 132 এবং 1432 এর প্যাকিং ঘনত্বের গুণফল, প্রায় 0.19658। এটি 1342 এর সুনির্দিষ্ট প্যাকিং ঘনত্ব বলে অনুমান করা হয়। Presutti & Stromquist (2010) 2413 এর প্যাকিং ঘনত্বে একটি নিম্ন সীমা প্রদান করেছে। এই নিম্ন সীমা, যা একটি অবিচ্ছেদ্য পরিপ্রেক্ষিতে প্রকাশ করা যেতে পারে, আনুমানিক 0.10474, এবং এটি প্রকৃত প্যাকিং ঘনত্ব বলে অনুমান করা হয়। [২৯]

সুপারপ্যাটার্নস[সম্পাদনা]

A k - সুপারপ্যাটার্ন হল একটি পারমুটেশন যাতে k দৈর্ঘ্যের সমস্ত ক্রমিউটেশন থাকে। উদাহরণস্বরূপ, 25314 হল একটি 3-সুপারপ্যাটার্ন কারণ এতে 3 দৈর্ঘ্যের সমস্ত 6টি পারমুটেশন রয়েছে। এটা জানা যায় যে k -superpatterns এর দৈর্ঘ্য কমপক্ষে k 2 / e 2 থাকতে হবে, যেখানে e ≈ 2.71828 হল অয়লারের সংখ্যা, [৩০] এবং দৈর্ঘ্যের k -সুপার প্যাটার্ন রয়েছে ⌈( k 2 + 1)/2⌉। [৩১] এই ঊর্ধ্ব সীমা নিম্ন-অর্ডার শর্তাবলী পর্যন্ত সর্বোত্তম সম্ভব বলে অনুমান করা হয়। [৩২]

সাধারণীকরণ[সম্পাদনা]

"প্যাটার্ন" ধারণাটি সাধারণীকরণ করা হয়েছে এমন বিভিন্ন উপায় রয়েছে। উদাহরণ স্বরূপ, একটি ভিনকুলার প্যাটার্ন হল ড্যাশ সমন্বিত একটি পারমুটেশন যা এন্ট্রিগুলিকে নির্দেশ করে যা ধারাবাহিকভাবে ঘটতে হবে না (সাধারণ প্যাটার্নের সংজ্ঞায়, কোনো এন্ট্রি ধারাবাহিকভাবে ঘটতে হবে না)। উদাহরণস্বরূপ, পারমুটেশন 314265-এ ড্যাশড প্যাটার্ন 2-31-4 এর দুটি কপি রয়েছে, যা 3426 এবং 3425 এন্ট্রি দ্বারা দেওয়া হয়েছে। একটি ড্যাশড প্যাটার্ন β এবং যেকোনো স্থানান্তর π-এর জন্য, আমরা π-এ β-এর কপি সংখ্যার জন্য β(π) লিখি। এইভাবে π-এ বিপরীতের সংখ্যা হল 2-1(π), যখন অবতরণ সংখ্যা হল 21(π)। যাওয়া আরো π মধ্যে উপত্যকার সংখ্যা 213 (π) + + 312 (π), যখন পীক সংখ্যা 231 (π) + + 132 (π) হয়। Babson & Steingrímsson (2000) দ্বারা প্রবর্তিত হয়েছিল, যিনি দেখিয়েছিলেন যে প্রায় সমস্ত পরিচিত মহোনিয়ান পরিসংখ্যানগুলি ভিনকুলার পারমিউটেশনের ক্ষেত্রে প্রকাশ করা যেতে পারে। [৩৩] উদাহরণস্বরূপ, π-এর প্রধান সূচক 1-32(π) + 2-31(π) + 3-21(π) + 21(π) এর সমান।

আরেকটি সাধারণীকরণ হল একটি ব্যারেড প্যাটার্ন, যাতে কিছু এন্ট্রি নিষিদ্ধ করা হয়। π-এর জন্য বাধা প্যাটার্ন এড়ানোর জন্য β মানে হল π-এর প্রতিটি এন্ট্রির সেট যা β-এর অ-বারিত এন্ট্রিগুলির একটি অনুলিপি তৈরি করে β-এর সমস্ত এন্ট্রিগুলির একটি অনুলিপি তৈরি করতে প্রসারিত করা যেতে পারে। West (1993) তার পারমুটেশনের গবেষণায় এই ধরনের নিদর্শনগুলি প্রবর্তন করেছিলেন যা একটি স্ট্যাকের মধ্য দিয়ে দুবার পাস করে সাজানো যেতে পারে। [৩৪] (উল্লেখ্য যে একটি স্ট্যাকের মাধ্যমে দুইবার সাজানোর ওয়েস্টের সংজ্ঞাটি সিরিজে দুটি স্ট্যাকের সাথে সাজানোর মত নয়। ) বর্ধিত নিদর্শনগুলির আরেকটি উদাহরণ Bousquet-Mélou & Butler (2007) রচনায় দেখা যায়, যিনি দেখিয়েছিলেন যে π এর সাথে সম্পর্কিত Schubert জাত স্থানীয়ভাবে ফ্যাক্টরিয়াল যদি এবং শুধুমাত্র যদি π 1324 এবং 21 3 54 [৩৫]

তথ্যসূত্র[সম্পাদনা]

  1. MacMahon, Percy A. (১৯১৫), Combinatory Analysis, London: Cambridge University Press, Volume I, Section III, Chapter V .
  2. MacMahon (1915), Items 97 and 98.
  3. Knuth, Donald E. (১৯৬৮), The Art Of Computer Programming Vol. 1, Boston: Addison-Wesley, আইএসবিএন 0-201-89683-4, এমআর 0286317, ওসিএলসি 155842391 ..
  4. Knuth (1968), Section 2.2.1, Exercises 4 and 5.
  5. Knuth (1968), Section 2.2.1, Exercise 13, rated M49 in the first printing, and M48 in the second.
  6. Tarjan, Robert (১৯৭২), "Sorting using networks of queues and stacks", Journal of the ACM, 19 (2): 341–346, এমআর 0298803, এসটুসিআইডি 13608929, ডিওআই:10.1145/321694.321704 .
  7. Pratt, Vaughan R. (১৯৭৩), "Computing permutations with double-ended queues. Parallel stacks and parallel queues", Proc. Fifth Annual ACM Symposium on Theory of Computing (Austin, Tex., 1973), পৃষ্ঠা 268–277, এমআর 0489115, এসটুসিআইডি 15740957, ডিওআই:10.1145/800125.804058 .
  8. Rosenstiehl, Pierre; Tarjan, Robert (১৯৮৪), "Gauss codes, planar Hamiltonian graphs, and stack-sortable permutations", Journal of Algorithms, 5 (3): 375–390, এমআর 0756164, ডিওআই:10.1016/0196-6774(84)90018-X .
  9. Simion, Rodica; Schmidt, Frank W. (১৯৮৫), "Restricted permutations", European Journal of Combinatorics, 6 (4): 383–406, এমআর 0829358, ডিওআই:10.1016/s0195-6698(85)80052-4অবাধে প্রবেশযোগ্য .
  10. Claesson, Anders; Kitaev, Sergey (২০০৮), "Classification of bijections between 321- and 132-avoiding permutations" (PDF), Séminaire Lotharingien de Combinatoire, 60: B60d, arXiv:0805.1325অবাধে প্রবেশযোগ্য, এমআর 2465405, বিবকোড:2008arXiv0805.1325C, ৪ মার্চ ২০১৬ তারিখে মূল (PDF) থেকে আর্কাইভ করা, সংগ্রহের তারিখ ২৮ অক্টোবর ২০২১ .
  11. Stankova, Zvezdelina (১৯৯৪), "Forbidden subsequences", Discrete Mathematics, 132 (1–3): 291–316, এমআর 1297387, ডিওআই:10.1016/0012-365X(94)90242-9অবাধে প্রবেশযোগ্য .
  12. Stankova, Zvezdelina; West, Julian (২০০২), "A New class of Wilf-Equivalent Permutations", Journal of Algebraic Combinatorics, 15 (3): 271–290, arXiv:math/0103152অবাধে প্রবেশযোগ্য, এমআর 1900628, এসটুসিআইডি 13921676, ডিওআই:10.1023/A:1015016625432 .
  13. Backelin, Jörgen; West, Julian; Xin, Guoce (২০০৭), "Wilf-equivalence for singleton classes", Advances in Applied Mathematics, 38 (2): 133–149, এমআর 2290807, ডিওআই:10.1016/j.aam.2004.11.006অবাধে প্রবেশযোগ্য .
  14. Bóna, Miklós (১৯৯৭), "Exact enumeration of 1342-avoiding permutations: a close link with labeled trees and planar maps", Journal of Combinatorial Theory, Series A, 80 (2): 257–272, arXiv:math/9702223অবাধে প্রবেশযোগ্য, এমআর 1485138, এসটুসিআইডি 18352890, ডিওআই:10.1006/jcta.1997.2800, বিবকোড:1997math......2223B .
  15. Gessel, Ira M. (১৯৯০), "Symmetric functions and P-recursiveness", Journal of Combinatorial Theory, Series A, 53 (2): 257–285, এমআর 1041448, ডিওআই:10.1016/0097-3165(90)90060-Aঅবাধে প্রবেশযোগ্য .
  16. Marcus, Adam; Tardos, Gábor (২০০৪), "Excluded permutation matrices and the Stanley-Wilf conjecture", Journal of Combinatorial Theory, Series A, 107 (1): 153–160, এমআর 2063960, ডিওআই:10.1016/j.jcta.2004.04.002অবাধে প্রবেশযোগ্য .
  17. Wilf, Herbert (২০০২), "Patterns of permutations", Discrete Mathematics, 257 (2): 575–583, এমআর 1935750, ডিওআই:10.1016/S0012-365X(02)00515-0অবাধে প্রবেশযোগ্য .
  18. Sagan, Bruce; Vatter, Vince (২০০৬), "The Möbius function of a composition poset", Journal of Algebraic Combinatorics, 24 (2): 117–136, arXiv:math/0507485অবাধে প্রবেশযোগ্য, এমআর 2259013, এসটুসিআইডি 11283347, ডিওআই:10.1007/s10801-006-0017-4 .
  19. Burstein, Alexander; Jelinek, Vit; Jelinkova, Eva; Steingrimsson, Einar (২০১১), "The Möbius function of separable and decomposable permutations", Journal of Combinatorial Theory, Series A, 118 (1): 2346–2364, এমআর 2834180, এসটুসিআইডি 13978488, ডিওআই:10.1016/j.jcta.2011.06.002 .
  20. Brignall, Robert; Jelínek, Vit; Kynčl, Jan; Marchant, David (২০১৯), "Zeros of the Möbius function of permutations" (PDF), Mathematika, 65 (4): 1074–1092, এমআর 3992365, এসটুসিআইডি 53366318, ডিওআই:10.1112/S0025579319000251 
  21. Marchant, David (২০২০), "2413-balloon permutations and the growth of the Möbius function", Electronic Journal of Combinatorics, 27 (1): P1.7, ডিওআই:10.37236/8554অবাধে প্রবেশযোগ্য 
  22. Bose, Prosenjit; Buss, Jonathan F.; Lubiw, Anna (মার্চ ১৯৯৮), "Pattern matching for permutations", Information Processing Letters, 65 (5): 277–283, ডিওআই:10.1016/S0020-0190(97)00209-3 
  23. Guillemot, Sylvain; Marx, Daniel (২০১৪)। "Finding small patterns in permutations in linear time": 20। arXiv:1307.3073অবাধে প্রবেশযোগ্যআইএসবিএন 978-1-61197-338-9ডিওআই:10.1137/1.9781611973402.7 
  24. Bruner, Marie-Louise; Lackner, Martin (২০১৩), "The computational landscape of permutation patterns", Pure Mathematics and Applications, 24 (2): 83–101, arXiv:1301.0340অবাধে প্রবেশযোগ্য, বিবকোড:2013arXiv1301.0340B 
  25. Kubica, M.; Kulczyński, T.; Radoszewski, J.; Rytter, W.; Waleń, T. (২০১৩), "A linear time algorithm for consecutive permutation pattern matching", Information Processing Letters, 113 (12): 430–433, ডিওআই:10.1016/j.ipl.2013.03.015 
  26. Guillemot, Sylvain; Vialette, Stéphane (২০০৯), "Pattern matching for 321-avoiding permutations", Algorithms and Computation, Lecture Notes in Computer Science, 5878, পৃষ্ঠা 1064–1073, arXiv:1511.01770অবাধে প্রবেশযোগ্য, ডিওআই:10.1007/978-3-642-10631-6_107 
  27. Albert, Michael; Lackner, Marie-Louise; Lackner, Martin; Vatter, Vincent (২০১৬), "The complexity of pattern matching for 321-avoiding and skew-merged permutations", Discrete Mathematics & Theoretical Computer Science, 18 (2), arXiv:1510.06051অবাধে প্রবেশযোগ্য, বিবকোড:2015arXiv151006051A 
  28. Price, Alkes (১৯৯৭), Packing densities of layered patterns, Ph.D. thesis, University of Pennsylvania .
  29. Albert, Michael H.; Atkinson, M. D.; Handley, C. C.; Holton, D. A.; Stromquist, W. (২০০২), "On packing densities of permutations", Electronic Journal of Combinatorics, 9: Research article 5, 20 pp, এমআর 1887086, ডিওআই:10.37236/1622অবাধে প্রবেশযোগ্য .
  30. Arratia, Richard (১৯৯৯), "On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern", Electronic Journal of Combinatorics, 6: N1, এমআর 1710623, ডিওআই:10.37236/1477অবাধে প্রবেশযোগ্য .
  31. Engen, Michael; Vatter, Vincent (২০২১), "Containing all permutations", American Mathematical Monthly, 128 (1): 4–24, ডিওআই:10.1080/00029890.2021.1835384অবাধে প্রবেশযোগ্য 
  32. Eriksson, Henrik; Eriksson, Kimmo; Linusson, Svante; Wästlund, Johan (২০০৭), "Dense packing of patterns in a permutation", Annals of Combinatorics, 11 (3–4): 459–470, এমআর 2376116, এসটুসিআইডি 2021533, ডিওআই:10.1007/s00026-007-0329-7 .
  33. Babson, Erik; Steingrímsson, Einar (২০০০), "Generalized permutation patterns and a classification of the Mahonian statistics", Séminaire Lotharingien de Combinatoire, 44: Research article B44b, 18 pp, এমআর 1758852 .
  34. West, Julian (১৯৯৩), "Sorting twice through a stack", Theoretical Computer Science, 117 (1–2): 303–313, এমআর 1235186, ডিওআই:10.1016/0304-3975(93)90321-Jঅবাধে প্রবেশযোগ্য .
  35. Bousquet-Mélou, Mireille; Butler, Steve (২০০৭), "Forest-like permutations", Annals of Combinatorics, 11 (3–4): 335–354, arXiv:math/0603617অবাধে প্রবেশযোগ্য, এমআর 2376109, এসটুসিআইডি 31236417, ডিওআই:10.1007/s00026-007-0322-1 .

বহিঃসংযোগ[সম্পাদনা]

২০০৩ সাল থেকে প্রতি বছর পারমুটেশন প্যাটার্নের উপর একটি সম্মেলন অনুষ্ঠিত হচ্ছে:

  1. পারমুটেশন প্যাটার্নস 2003, ফেব্রুয়ারি 10-14, 2003, ওটাগো বিশ্ববিদ্যালয়, ডুনেডিন, নিউজিল্যান্ড।
  2. পারমুটেশন প্যাটার্নস 2004, 5-9 জুলাই, 2004, মালাস্পিনা ইউনিভার্সিটি-কলেজ, নানাইমো, ব্রিটিশ কলাম্বিয়া, কানাডা।
  3. পারমুটেশন প্যাটার্নস 2005, মার্চ 7-11, 2005, ইউনিভার্সিটি অফ ফ্লোরিডা, গেইনসভিল, ফ্লোরিডা, মার্কিন যুক্তরাষ্ট্র।
  4. পারমুটেশন প্যাটার্নস 2006, জুন 12-16, 2006, রেইক্যাভিক ইউনিভার্সিটি, রেইক্যাভিক, আইসল্যান্ড।
  5. পারমুটেশন প্যাটার্নস 2007, 11-15 জুন, 2007, সেন্ট অ্যান্ড্রুজ বিশ্ববিদ্যালয়, সেন্ট অ্যান্ড্রুজ, স্কটল্যান্ড।
  6. পারমুটেশন প্যাটার্নস 2008, জুন 16-20, 2008, ওটাগো ইউনিভার্সিটি, ডুনেডিন, নিউজিল্যান্ড।
  7. পারমুটেশন প্যাটার্নস 2009 ওয়েব্যাক মেশিনে আর্কাইভকৃত ৪ মার্চ ২০১৬ তারিখে, জুলাই 13-17, 2009, Università di Firenze, ফ্লোরেন্স, ইতালি।
  8. পারমুটেশন প্যাটার্নস 2010, আগস্ট 9-13, 2010, ডার্টমাউথ কলেজ, হ্যানোভার, নিউ হ্যাম্পশায়ার, মার্কিন যুক্তরাষ্ট্র।
  9. পারমুটেশন প্যাটার্নস 2011, জুন 20-24, 2011, ক্যালিফোর্নিয়া পলিটেকনিক স্টেট ইউনিভার্সিটি, সান লুইস ওবিস্পো, ক্যালিফোর্নিয়া, মার্কিন যুক্তরাষ্ট্র।
  10. পারমুটেশন প্যাটার্নস 2012, 11-15 জুন, 2012, স্ট্র্যাথক্লাইড বিশ্ববিদ্যালয়, গ্লাসগো, স্কটল্যান্ড।
  11. পারমুটেশন প্যাটার্নস 2013, জুলাই 1-5, 2013, Université Paris Diderot, Paris, France.
  12. পারমুটেশন প্যাটার্নস 2014, 7-11 জুলাই, 2014, ইস্ট টেনেসি স্টেট ইউনিভার্সিটি, জনসন সিটি, টেনেসি, মার্কিন যুক্তরাষ্ট্র।
  13. পারমুটেশন প্যাটার্নস 2015, 15-19 জুন, 2015, ডি মরগান হাউস, লন্ডন, ইংল্যান্ড।
  14. পারমুটেশন প্যাটার্নস 2016, 27 জুন-জুলাই 1, 2016, হাওয়ার্ড ইউনিভার্সিটি, ওয়াশিংটন, ডিসি, ইউএসএ।
  15. পারমুটেশন প্যাটার্নস 2017, 26-30 জুন, 2017, রেইক্যাভিক ইউনিভার্সিটি, রেইকজাভিক, আইসল্যান্ড।
  16. পারমুটেশন প্যাটার্নস 2018, 9-13 জুলাই, 2018, ডার্টমাউথ কলেজ, হ্যানোভার, নিউ হ্যাম্পশায়ার, মার্কিন যুক্তরাষ্ট্র।
  17. পারমুটেশন প্যাটার্নস 2019, 17-21 জুন, 2019, ইউনিভার্সিটি জুরিখ, জুরিখ, সুইজারল্যান্ড।
  18. পারমুটেশন প্যাটার্নস 2020 ভার্চুয়াল ওয়ার্কশপ, 30 জুন-জুলাই 1, 2020, ভালপারাইসো ইউনিভার্সিটি, ভালপারাইসো, ইন্ডিয়ানা, ইউএসএ দ্বারা হোস্ট।
  19. পারমুটেশন প্যাটার্নস 2021 ভার্চুয়াল ওয়ার্কশপ, 15-16 জুন, 2021, ইউনিভার্সিটি অফ স্ট্র্যাথক্লাইড, গ্লাসগো, স্কটল্যান্ড দ্বারা আয়োজিত।

আমেরিকান ম্যাথমেটিকাল সোসাইটি নিম্নলিখিত মিটিংগুলিতে প্যাটার্নস ইন পারমুটেশনের বিশেষ অধিবেশন অনুষ্ঠিত হয়েছে:

অন্যান্য স্থানান্তর নিদর্শন মিটিং:

অন্যান্য লিঙ্ক: