التبديل القابل للفرز على المكدس

في الرياضيات وعلوم الحاسوب ، يُعرف التبديل القابل للفرز باستخدام المكدس (ويُسمى أيضًا تبديل الشجرة ) ^{[ 1 ]} بأنه تبديل يمكن فرز عناصره بواسطة خوارزمية يقتصر تخزينها الداخلي على بنية بيانات مكدس واحدة . التبديلات القابلة للفرز باستخدام المكدس هي تحديدًا التبديلات التي لا تحتوي على نمط التبديل 231؛ ويتم حسابها باستخدام أعداد كاتالان ، ويمكن وضعها في علاقة تقابل مع العديد من الكائنات التوافقية الأخرى التي لها نفس دالة العد، بما في ذلك مسارات ديك والأشجار الثنائية .

طُرحت مشكلة فرز سلسلة الإدخال باستخدام مكدس لأول مرة من قبل كنوت (1968) ، الذي قدم الخوارزمية الخطية التالية (المرتبطة ارتباطًا وثيقًا بخوارزميات مشكلة جميع القيم الأصغر الأقرب اللاحقة):

• قم بتهيئة مكدس فارغ
• لكل قيمة إدخال x :
  • طالما أن المكدس غير فارغ وقيمة x أكبر من العنصر العلوي في المكدس، قم بإخراج المكدس إلى المخرج.
  • ادفع x إلى المكدس
• طالما أن المكدس غير فارغ، قم بإخراج العنصر إلى المخرج.

لاحظ كنوت أن هذه الخوارزمية تُرتّب بعض سلاسل الإدخال بشكل صحيح، بينما تفشل في ترتيب سلاسل أخرى. على سبيل المثال، السلسلة 3، 2، 1 مُرتّبة بشكل صحيح: حيث تُضاف العناصر الثلاثة إلى المكدس، ثم تُزال منه بالترتيب 1، 2، 3. أما السلسلة 2، 3، 1 فليست مُرتّبة بشكل صحيح: إذ تُضيف الخوارزمية العنصر 2 أولًا، ثم تُزيله عندما ترى قيمة الإدخال الأكبر 3، مما يؤدي إلى إخراج 2 قبل 1 بدلًا من إخراجه بعده.

لأن هذه الخوارزمية تعتمد على فرز المقارنة ، فإن نجاحها أو فشلها لا يعتمد على القيم العددية لتسلسل الإدخال، بل على ترتيبها النسبي فقط؛ أي أنه يمكن وصف الإدخال بالتبديل اللازم لتكوينه من تسلسل مُرتب بنفس الطول. وقد وصف كنوت التبديلات التي تُرتبها هذه الخوارزمية بشكل صحيح بأنها التبديلات التي لا تحتوي على نمط التبديل 231: ثلاثة عناصر x و y و z ، تظهر في الإدخال بهذا الترتيب، حيث z  < x < y . علاوة على ذلك، لاحظ أنه إذا فشلت الخوارزمية في فرز إدخال ما، فلا يمكن فرز هذا الإدخال باستخدام مكدس واحد.   

بالإضافة إلى إلهام الكثير من الأعمال اللاحقة حول الفرز باستخدام أنظمة أكثر تعقيدًا من المكدسات وهياكل البيانات ذات الصلة، ^{[ 2 ]} أدى بحث كنوت إلى بدء دراسة أنماط التبديل وفئات التبديل المحددة بواسطة الأنماط المحظورة.

تشكل سلسلة عمليات الدفع والسحب التي تُنفذها خوارزمية فرز كنوت أثناء فرزها لتبديل قابل للفرز على المكدس لغة ديك : إذ يُنتج إعادة تفسير عملية الدفع كقوس مفتوح وعملية السحب كقوس مغلق سلسلة من الأقواس المتوازنة. علاوة على ذلك، تنشأ كل سلسلة ديك من تبديل قابل للفرز على المكدس بهذه الطريقة، وكل تبديلين مختلفين قابلين للفرز على المكدس يُنتجان سلسلتين ديك مختلفتين. لهذا السبب، فإن عدد التبديلات القابلة للفرز على المكدس ذات الطول n هو نفسه عدد سلاسل ديك ذات الطول 2^ n ، وهو عدد كاتالان.

${\displaystyle C_{n}={\frac {1}{n+1}}{\binom {2n}{n}}.}$^{[ 3 ]}

يمكن أيضًا ترجمة التباديل القابلة للفرز باستخدام المكدس مباشرةً من وإلى الأشجار الثنائية (غير المصنفة)، وهي فئة توافقية أخرى تعتمد دالة عدها على متتالية أعداد كاتالان. يمكن تحويل الشجرة الثنائية إلى تبديل قابل للفرز باستخدام المكدس عن طريق ترقيم عقدها من اليسار إلى اليمين ، ثم سرد هذه الأرقام بالترتيب الذي ستتم زيارتها به في عملية اجتياز الشجرة بترتيب ما قبل الترتيب: الجذر أولًا، ثم الشجرة الفرعية اليسرى، ثم الشجرة الفرعية اليمنى، مع الاستمرار بشكل متكرر داخل كل شجرة فرعية. في الاتجاه المعاكس، يمكن فك تشفير التبديل القابل للفرز باستخدام المكدس إلى شجرة حيث تتوافق القيمة الأولى x من التبديل مع جذر الشجرة، ويتم فك تشفير القيم x − 1 التالية بشكل متكرر لإعطاء الابن الأيسر للجذر، ويتم فك تشفير القيم المتبقية مرة أخرى بشكل متكرر لإعطاء الابن الأيمن. ^{[ 1 ]}  

يمكن أيضًا وضع عدة فئات أخرى من التباديل في علاقة تقابل مع التباديل القابلة للفرز على المكدس. على سبيل المثال، يمكن تكوين التباديل التي تتجنب الأنماط 132 و213 و312 على التوالي من التباديل القابلة للفرز على المكدس (التي تتجنب النمط 231) عن طريق عكس التبديل، أو استبدال كل قيمة x في التبديل بـ n  +  1 − x ، أو الجمع بين العمليتين. كما أن التباديل التي تتجنب النمط 312 هي معكوسات التباديل التي تتجنب النمط 231، وقد سُميت بالتباديل القابلة للتحقيق على المكدس لأنها التباديل التي يمكن تكوينها من التبديل المحايد من خلال سلسلة من عمليات الدفع من المدخلات والسحب من المخرجات على المكدس. ^{[ 4 ]} كما لاحظ كنوت (1968) ، فإن التبديلات التي تتجنب 123 والتبديلات التي تتجنب 321 لها نفس وظيفة العد على الرغم من أنها أقل ارتباطًا بشكل مباشر بالتبديلات القابلة للفرز بالمكدس.  

قام روتيم (1981) بدراسة خصائص التبديلات القابلة للفرز باستخدام المكدس، والتي تم اختيارها عشوائيًا وبشكل منتظم من بين جميع التبديلات ذات الطول المحدد. ويُحسب الطول المتوقع لأطول سلسلة فرعية تنازلية في مثل هذا التبديل على النحو التالي:${\displaystyle {\sqrt {\pi n}}-O(1)}$، وتختلف بمعامل ثابت عن التباديل العشوائية غير المقيدة (التي يبلغ طولها المتوقع تقريبًا${\displaystyle 2{\sqrt {n}}}$يختلف الطول المتوقع لأطول سلسلة تصاعدية اختلافًا أكبر عن التباديل غير المقيدة: فهو ${\displaystyle (n+1)/2}$العدد المتوقع للقيم داخل التبديل التي تكون أكبر من جميع القيم السابقة هو فقط${\displaystyle 3-6/(n+2)}$أصغر من قيمتها اللوغاريتمية للتباديل غير المقيدة. والعدد المتوقع للانقلابات هو${\displaystyle \Theta (n^{3/2})}$، على النقيض من قيمتها${\displaystyle \Theta (n^{2})}$للتباديل غير المقيدة.

كل تبديل يُعرّف رسمًا بيانيًا للتبديل ، وهو رسم بياني رؤوسه هي عناصر التبديل، وحوافه تربط أزواج العناصر التي تم عكسها بواسطة التبديل. رسوم التبديل للتبديلات القابلة للفرز المكدس مثالية بشكل بديهي . ^{[ 4 ]}

لكل عنصر i _من التبديل p ، عرّف bᵢ على أنه عدد العناصر الأخرى التي تقع على يسار i وأكبر منه . عندئذٍ يكون التبديل p قابلاً للفرز باستخدام المكدس إذا وفقط إذا كان ، لكل i ، bᵢ ₋ bᵢ _{+ 1} ≤ _1. ^{[ 1 ]}      

يستخدم Knott (1977) التقابل بين التبديلات القابلة للفرز المكدس والأشجار الثنائية لتحديد رتبة عددية لكل شجرة ثنائية، ولإنشاء خوارزميات فعالة لحساب رتبة الشجرة ("الترتيب") ولحساب الشجرة ذات الرتبة المعطاة ("فك الترتيب").

عرّف ميشيلي وروسين (2006) عمليتين للتحرير على التباديل: الحذف (لإنشاء نمط تبديل ) ومعكوسه. وباستخدام نفس العلاقة بين الأشجار والتباديل، لاحظا أن هاتين العمليتين تُقابلان انكماش الحواف في الشجرة ومعكوسها. وبتطبيق خوارزمية برمجة ديناميكية ذات زمن متعدد الحدود لحساب مسافة التحرير في الأشجار، أظهرا أنه يمكن إيجاد مسافة التحرير بين تبديلين قابلين للفرز المكدسي (وبالتالي أطول نمط مشترك) في زمن متعدد الحدود. وقد عُممت هذه التقنية لاحقًا لتشمل خوارزميات إيجاد أطول الأنماط المشتركة للتباديل القابلة للفصل ؛ ^{[ 5 ]} ومع ذلك، فإن مسألة أطول نمط مشترك تُصنف ضمن مسائل NP-كاملة للتباديل العشوائية. ^{[ 6 ]}

• أفيس، ديفيد ؛ نيوبورن، مونرو (1981)، "حول مجموعات النبضات المتسلسلة"، Utilitas Mathematica ، 19 : 129-140 ، MR 0624050 .
• بونا، ميكلوس (2002)، "دراسة استقصائية لتخصصات فرز المكدس" ، المجلة الإلكترونية للتوافقية ، 9 (2) A1، doi : 10.37236/1693 ، MR 2028290 .
• بوفيل، ماتيلد؛ روسين، دومينيك؛ فياليت، ستيفان (2007)، "أطول نمط قابل للفصل بين التباديل"، مطابقة الأنماط التوافقية (CPM 2007) ، سلسلة محاضرات في علوم الحاسوب، المجلد  4580، سبرينغر، الصفحات 316-327 ، doi : 10.1007/978-3-540-73437-6_32 ، ISBN  978-3-540-73436-9.
• فيلسنر، ستيفان؛ بيرجل، مارتن (2008)، "تعقيد الفرز باستخدام شبكات من المكدسات والطوابير"، الخوارزميات - ESA 2008 ، سلسلة محاضرات في علوم الحاسوب، المجلد  5193، كارلسروه، ألمانيا، الصفحات 417-429 ، doi : 10.1007/978-3-540-87744-8_35 ، ISBN  978-3-540-87743-1{{citation}}: CS1 maint: موقع الناشر مفقود ( رابط ) .
• نوت، غاري د. (فبراير 1977)، "نظام ترقيم للأشجار الثنائية"، اتصالات رابطة آلات الحوسبة ، 20 (2): 113-115 ، doi : 10.1145/359423.359434.
• كنوت، دونالد (1968)، "المجلد 1: الخوارزميات الأساسية"، فن برمجة الحاسوب ، ريدينغ، ماساتشوستس: أديسون-ويسلي.
• ميشيلي، آن؛ روسين، دومينيك (2006)، "مسافة التحرير بين الأشجار المرتبة غير المصنفة"، المعلوماتية النظرية وتطبيقاتها ، 40 (4): 593-609 ، arXiv : math/0506538 ، doi : 10.1051/ita:2006043 ، MR 2277052 ، S2CID 2259835  .
• روزنستيل، بيير ؛ تارجان، روبرت إي. (1984)، "رموز غاوس، ورسوم بيانية هاميلتونية مستوية، وتباديل قابلة للفرز المكدس"، مجلة الخوارزميات ، 5 (3): 375-390 ، doi : 10.1016/0196-6774(84)90018-X ، MR 0756164 
• روتيم، د. (1981)، "التباديل القابلة للفرز باستخدام المكدس"، الرياضيات المتقطعة ، 33 (2): 185-196 ، doi : 10.1016/0012-365X(81)90165-5 ، MR 0599081 .
• تارجان، روبرت (أبريل 1972)، "الفرز باستخدام شبكات الطوابير والمكدسات"، مجلة ACM ، 19 (2): 341-346 ، doi : 10.1145/321694.321704.