نمایش مبدأ برای وارونگی (ریاضیات گسسته)

[[پرونده:Inversion qtl1.svg|بندانگشتی|به یکی از وارونگی‌های جایگشت فوق اشاره شده‌است.{{سخ}}وارونگی یک جایگشت توسط جفت اندیس (۲،۴) یا جفت عناصر (۵،۲) تعیین می‌شود.|285x285px]]
در علوم کامپیوتر و ریاضیات گسسته، دنباله‎ای '''وارونگی''' دارد که دو عنصر آن از [[ترتیب کامل|نظم]] عادی خود خارج هستند. تعداد وارونگی‎های یک جایگشت به ما نشان می‎دهد که آن جایگشت تا چه‎حد از نظم طبیعی(همان ترتیب عادی)خود خارج است.

== تعاریف ==
=== وارونگی ===
<math>\pi</math> را جایگشتی دلخواه درنظربگیرید. اگر در جایگشت <math>\pi</math>، <math>i < j</math> و <math>\pi(i) > \pi(j)</math> باشد، آنگاه جفت اندیس <math>(i, j)</math>{{Sfn|Aigner|2007}}{{Sfn|Comtet|1974}} یا جفت عنصر <math>\bigl(\pi(i), \pi(j)\bigr)</math>{{Sfn|Knuth|1973}}{{Sfn|Pemmaraju|Skiena|2003}}{{Sfn|Vitter|Flajolet|1990}}، یک وارونگی از جایگشت <math>\pi</math> نامیده می‌شوند.

وارونگی معمولاً برای جایگشت‌ها تعریف می‌شود، ولی امکان دارد برای دنباله نیز تعریف شود:

<math>S</math> را یک دنباله (یا جایگشت [[چندمجموعه|Multi Set]] {{Sfn|Bóna|2012}})درنظر بگیرید. اگر <math>i < j</math> و <math>S(i) > S(j)</math> باشد، به دو اندیس <math>(i, j)</math> {{Sfn|Bóna|2012}} {{Sfn|Cormen|Leiserson|Rivest|Stein|2001}} یا دو عنصر <math>\bigl(S(i), S(j)\bigr)</math> {{Sfn|Barth|Mutzel|2004}} وارونگی <math>S</math> گفته می‌شود.

برای دنباله‌ها، وارونگی‌ها طبق تعریف مبتنی بر عنصر، یکتا نیستند، زیرا امکان دارد جفت اندیس‌های متفاوت مقادیر یکسانی داشته باشند.

'''مجموعه وارونگی،''' مجموعه همه وارونگی‌ها است. مجموعهٔ وارونگی یک جایگشت با توجه به تعریف مبتنی بر مکان، همان است که از [[جایگشت|معکوس]] مجموعه وارونگی جایگشت با توجه به تعریف مبتنی بر عنصر به دست می‎آید و بالعکس، {{Sfn|Gratzer|2016}} تنها با رد و بدل عناصر از جفت‌ها.

=== شماره وارونگی ===
'''عدد وارونگی''' شاخص بارز مجموعه وارونگی است. این یک اندازه‌گیری رایج از مرتب‌سازی یک جایگشت {{Sfn|Vitter|Flajolet|1990}} یا دنباله است. {{Sfn|Barth|Mutzel|2004}}

عدد وارونگی تعداد برخوردها در نمودار پیکانی جایگشت است، {{Sfn|Gratzer|2016}} [[فاصله Kendall tauhttps://en.wikipedia.org/wiki/Kendall tau distance|فاصله Kendall tau]] آن، از جایگاه اصلی و جمع هر یک از بردارهای مربوط به وارونگی که در زیر تعریف شده‌است.

مهم نیست که از تعریف مبتنی بر مکان یا مبتنی بر عنصر وارونگی برای تعریف عدد وارونگی استفاده شود، زیرا یک جایگشت و معکوس آن دارای تعداد وارونگی‎های یکسانی هستند.

دیگر اندازه‌گیری‌های (پیش-) مرتب‌سازی شامل حداقل تعداد عناصری که می‌توانند از دنباله حذف شوند تا یک دنباله کاملاً مرتب حاصل شود، تعداد و طول «اجراهای» مرتب شده در داخل دنباله، Spearman Footrule (مجموع فاصله‌های هر عنصر از مکان قرارگیری آن پس از مرتب‌سازی) و کمترین تعداد جابجایی مورد نیاز برای مرتب‌سازی دنباله است. {{Sfn|Mahmoud|2000}} الگوریتم‌های [[مرتب‌سازی مقایسه‌ای|مرتب‌سازی مقایسه]] استاندارد می‌توانند برای محاسبه تعداد وارونگی در زمان {{ریاضی|O(''n'' log ''n'')}} سازگار شوند.

=== بردارهای مربوط به وارونگی ===
سه بردار مشابه در حال استفاده هستند که وارونگی‌های یک جایگشت را در یک بردار خلاصه می‌کنند که آن جایگشت را به‌طور یکتایی مشخص می‌کند. آنها معمولاً ''بردار وارونگی'' یا ''کد لیمر'' نامیده می‌شوند. (لیستی از منابع در [[wikiti:Inversion (discrete mathematics)#Sources|اینجا]] یافت می‌شود )

این مقاله از اصطلاح ''بردار وارونگی استفاده می‌کند'' (<math>v</math>) مثل [[متمتیکا|ولفرام]]<ref>[[:en:Eric W. Weisstein|Weisstein, Eric W.]] [http://mathworld.wolfram.com/.html "Inversion Vector"]</ref>. دو بردار باقی مانده گاهی ''بردار وارونگی'' ''چپ'' و ''راست'' نامیده ''می‌شوند''، اما برای پیشگیری از اشتباه گرفتن با بردار وارونگی این مقاله آن‎ها ''را تعداد معکوس چپ'' (<math>l</math>) و ''تعداد معکوس راست'' (<math>r</math>)می‌نامد.

بعنوان عدد [[فاکتوریل]] تعبیر شده‌است. تعداد وارونگی سمت چپ جایگشت‌ها، شاخصreverse colexicographic<ref>Reverse colex order of finitary permutations {{OEIS|A055089}}</ref> و تعداد وارونگی سمت راست آن‎ها، شاخص lexicographic را در اختیار ما قرار می‌دهد.
[[پرونده:Inversion example; Rothe 1.svg|بندانگشتی|نمودار روته|334x334px]]
'''بردار وارونگی''' (<math>v</math>)''' :''' با توجه به تعریف ''مبتنی بر عنصر،'' <math>v(i)</math> همان تعداد وارونگی‌هایی است که مؤلفه ''کوچکتر'' (سمت راست) آن‎ها <math>i</math> است. {{Sfn|Knuth|1973}}

<math>v(i)</math> تعداد عناصر موجود در <math>\pi</math> است که از <math>i</math> بزرگترند و قبل از <math>i</math> قرار دارند.

:<math display="block">v(i) ~~=~~ \# \{ k \mid k > i ~\land~ \pi^{-1}(k) < \pi^{-1}(i) \}</math>

'''تعداد معکوس سمت چپ''' (<math>l</math>)''' :''' با تعریف ''مبتنی به مکان،'' <math>l(i)</math> تعداد وارونگی‌هایی است که مؤلفه ''بزرگتر'' (راست) آن‎ها ''<math>i</math>'' است.

<math>l(i)</math> تعداد عناصر موجود در <math>\pi</math> بزرگتر از <math>\pi(i)</math> قبل از <math>\pi(i)</math> .

:<math display="block">l(i) ~~=~~ \# \left\{ k \mid k < i ~\land~ \pi(k) > \pi(i) \right\}</math>

'''تعداد معکوس سمت راست''' ('''<math>r</math>''') ''':''' (اغلب به نام ''[[:en:Lehmer code|کد لیمر]]'' خوانده می‌شود)

با تعریف مبتنی بر ''مکان،'' <math>r(i)</math> تعداد وارونگی‌هایی است که مؤلفه ''کوچکتر'' (سمت چپ) آنها <math>i</math> است.

<math>r(i)</math> تعداد عناصری است که در <math>\pi</math> قرار دارند، از <math>\pi(i)</math> کوچکترند و بعد از <math>\pi(i)</math> قرار گرفته‌اند.<math display="block">r(i) ~~=~~ \# \{ k \mid k > i ~\land~ \pi(k) < \pi(i) \}</math>

<math>v</math> و <math>r</math>، هردو را می‌توان به کمک '''[http://www.mathe2.uni-bayreuth.de/frib/html/book/hyl00_30.html نمودار روته]''' یافت؛ که یک ماتریس جابگشت، با ۱هایی است که توسط نقاط نشان داده می‌شوند و یک وارونگی (که اغلب توسط یک صلیب نمایش داده می‌شود) در هر موقعیتی که دارای نقطه ای در سمت راست و زیر آن است، مشخص می‌شود. <math>r(i)</math> مجموع وارونگی‌های موجود در ردیف i ام نمودار روته است، در حالی که <math>v(i)</math> مجموع وارونگی‌های موجود در ستون i ام نمودار روته است. ماتریس جایگشت معکوس، [[ترانهاده]] شده ماتریس اولیه است بنابراین مؤلفه <math>v</math> یک جایگشت، مؤلفه <math>r</math> معکوس آن می‌باشد و بلعکس.

=== مثال: همه جایگشت‌های چهار عنصر ===
[[پرونده:2-element subsets of 4 elements; array, hexagonal.svg|بندانگشتی|شش وارونگی محتمل یک جابه جایی با ۴ عنصر|308x308px]]
جدول مرتب‌سازی زیر ۲۴ جایگشت حاصل از چهار عنصر با مجموعه‌های وارونگی مکان محور آنها، بردارهای مربوط به وارونگی و اعداد وارونگی را نشان می‌دهد. (ستون‌های کوچک بازتاب ستون‌هایی هستند که در کنار آنها قرار دارند و می‌توان از آنها برای مرتب کردنشان به ترتیب colexicographic استفاده کرد)

مشاهده می‌شود که <math>v</math> و <math>l</math> همیشه ارقام مشابهی دارند و این <math>l</math> و <math>r</math> هر دو مرتبط به مجموعه وارونگی مکان محور هستند. عناصر غیرمستقیم <math>l</math> جمع نمودارهای نزولی مثلث نمایش داده شده و همین موارد از <math>r</math> جمع نمودارهای صعودی آن هستند. (جفت‌های موجود در نمودارهای نزولی دارای مؤلفه‌های راست ۲، ۳، ۴ مشترک هستند، در حالی که جفت‌های موجود در نمودارهای صعودی دارای مؤلفه‌های چپ ۱، ۲، ۳ مشترک هستند). )

ترتیب پیش فرض جدول، ترتیب reverse colexicographic جایگشت <math>\pi</math> است، که همان ترتیب colexicographic  <math>l</math> است. ترتیب lexicographic  <math>\pi</math>، همان ترتیب lexicographic  <math>r</math> است.

==== ترتیب lexicographic :<ref>[[:en:Lexicographical order#Colexicographic order|Lexicographic & Colexicographic order]]</ref> ====
در ریاضیات ترتیب lexicographic یا (ترتیب الفبایی) نوعی سازماندهی است که در آن کلمات به‎ترتیب الفبایی براساس ترتیب الفبایی حروف تشکیل دهنده‎ی آن‎ها مرتب می‎شوند. همچنین اگر طول دو کلمه باهم متفاوت بود کلمه با طول کمتر اولویت پیدا می‎کند. این نوع سازمان‎دهی به‎صورت کلی در مورد دنباله‎هایی به‎کار می‎روند که

اعضای آن‎ها متناهی باشند و از یک جامعه خاص و متناهی انتخاب شوند که به این جامعه الفبا گفته می‎شود. در مباحث علوم کامپیوتر چنین دنباله‎هایی به‎اصطلاح رشته‎ای از کاراکترها یا ارقام نامیده می‎شوند. به‎طوز مثال با این ترتیب داریم : 25 < 34

==== ترتیب colexicographic ====
این ترتیب به‎طریقی در مقابل ترتیب lexicographic قرار دارد. چون در ترتیب lexicographic به‎دنبال اولین رقم از سمت چپ می‎باشیم که با رقم در همین جایگاه از یک دنباله

دیگر متفاوت باشد اما در ترتیب colexicographic، ما به‎دنبال آخرین رقم از سمت چپ (اولین رقم از سمت راست) می‎باشیم که با رقم موجود در همین جایگاه از دنباله دیگر

متفاوت باشد. به‎طور مثال با ترتیب colexicographic داریم : 34 < 25

== ترتیب ضعیف جایگشت ==
[[پرونده:Symmetric group 4; permutohedron 3D; numbers.svg|بندانگشتی| جایگشتی از [[گروه متقارن]] S <sub>4</sub>|313x313px]]
مجموعه جایگشت‌های ''n مورد،'' می‌تواند ساختار یک [[مجموعه جزئاً مرتب|دستورالعمل جزئی]] را بدهد، که '''ترتیب ضعیف جایگشت‌ها''' نامیده می‌شود، و یک [[مشبکه (ترتیب)|شبکه]] تشکیل می‌دهد.

[[:en:Hasse diagram|نمودار هسه]] مجموعه‌های وارونگی که توسط رابطه زیرمجموعه ای مرتب شده، اسکلت یک <nowiki>permutohedron</nowiki> را تشکیل می‌دهد.

اگر یک جایگشت به هر مجموعه وارونگی، با استفاده از تعریف مبتنی بر مکان اختصاص داده شود، نظم حاصل از جایگشت‌ها، همان permutohedron است، که در آن یک لبه مربوط به مبادله دو عنصر با مقادیر متوالی است. این ترتیب ضعیف جایگشت است. اگر یک جایگشت به هر مجموعه وارونگی با استفاده از تعریف مبتنی بر مکان تخصیص داده شود، نظم حاصل یک گراف Cayley خواهد بود، که در آن یک لبه مربوط به تعویض دو عنصر موجود در مکان‌های متوالی است. این نمودار Cayley از یک گروه متقارن، مشابه با permutohedron است، اما با جایگزینی هر جایگشت با معکوس آن حاصل می‌شود.

== جستارهای وابسته ==
* [[:en:Factorial number system|Factorial number system]]
* [[:en:Permutation graph|Permutation graph]]
*[[:en:Permutation group#Transpositions, simple transpositions, inversions and sorting|Transpositions, simple transpositions, inversions and sorting]]
* [[:en:Damerau–Levenshtein distance|Damerau–Levenshtein distance]]
* [[:en:Parity of a permutation|Parity of a permutation]]

'''توالی‌های موجود در [[دانشنامه برخط دنباله‌های صحیح|OEIS]] :'''
* [[oeis:wiki/Index to OEIS: Section Fa#facbase|توالی‌های مربوط به نمایندگی پایگاه فاکتوریل]]
* شماره‌های {{OEIS link|A007623}}: {{OEIS link|A007623}} و {{OEIS link|A108731}}
* شماره‌های وارونگی: {{OEIS link|A034968}}
* مجموعه‌های وارونگی از {{OEIS link|A211362}} محدود که به عنوان اعداد باینری تعبیر می‌شوند: {{OEIS link|A211362}} (جایگشت مرتبط: {{OEIS link|A211363}})
* {{OEIS link|A059590}} محدود که تنها ۰ و ۱ ثانیه در بردارهای وارونگی خود دارند: {{OEIS link|A059590}} (مجموعه‌های وارونگی آنها: {{OEIS link|A211364}})
* تعداد جایگشت عناصر ''n'' با وارونگی ''k''؛ شماره {{OEIS link|A008302}}: {{OEIS link|A008302}} (حداکثر ردیف آنها؛ شماره‌های کندال مان: {{OEIS link|A000140}})
* تعدادی از نمودار برچسب متصل با لبه‌های ''n'' و ''n'' گره: {{OEIS link|A057500}}

== منابع ==
{{پانویس|۳}}

=== کتابشناسی منبع ===
{{آغاز پانویس|۱}}
* {{Cite book|ref=harv|last=Aigner|first=Martin|title=A course in enumeration|chapter=Word Representation|publisher=Springer|location=Berlin, New York|year=2007|isbn=3-642-07253-4}}
* {{Cite journal|last=Barth|first=Wilhelm|last2=Mutzel|first2=Petra|author-link2=Petra Mutzel|year=2004|title=Simple and Efficient Bilayer Cross Counting|journal=[[Journal of Graph Algorithms and Applications]]|volume=8|issue=2|pages=179&ndash;194|doi=10.7155/jgaa.00088|ref=harv}}
* {{Cite book|ref=harv|last=Bóna|first=Miklós|authorlink=Miklós Bóna|title=Combinatorics of permutations|chapter=2.2 Inversions in Permutations of Multisets|publisher=CRC Press|location=Boca Raton, FL|year=2012|isbn=1-4398-5051-8}}
* {{Cite book|ref=harv|last=Comtet|first=Louis|title=Advanced combinatorics; the art of finite and infinite expansions|url=https://archive.org/details/Comtet_Louis_-_Advanced_Coatorics|chapter=6.4 Inversions of a permutation of [n]|publisher=D. Reidel Pub. Co|location=Dordrecht,Boston|year=1974|isbn=9027704414}}
* {{Cite book|ref=harv|last4=Stein|isbn=0-262-53196-8|year=2001|publisher=MIT Press and McGraw-Hill|title=[[Introduction to Algorithms]]|authorlink4=Clifford Stein|first4=Clifford|authorlink3=Ron Rivest|first=Thomas H.|first3=Ronald L.|last3=Rivest|authorlink2=Charles E. Leiserson|first2=Charles E.|last2=Leiserson|authorlink=Thomas H. Cormen|last=Cormen|edition=2nd}}
* {{Cite book|ref=harv|last=Gratzer|first=George|authorlink=George Grätzer|title=Lattice theory. special topics and applications|chapter=7-2 Basic objects|publisher=Birkhäuser|location=Cham, Switzerland|year=2016|isbn=3-319-44235-X}}
* {{Cite book|ref=harv|last=Knuth|first=Donald|title=[[The art of computer programming]]|chapter=5.1.1 Inversions|publisher=Addison-Wesley Pub. Co|year=1973|isbn=0-201-89685-0}}
* {{Cite book|ref=harv|title=Sorting: a distribution theory|chapter=Sorting Nonrandom Data|volume=54|series=Wiley-Interscience series in discrete mathematics and optimization|first=Hosam Mahmoud|last=Mahmoud|publisher=Wiley-IEEE|year=2000|isbn=978-0-471-32710-3}}
* {{Cite book|ref=harv|title=Computational discrete mathematics: combinatorics and graph theory with Mathematica|url=https://archive.org/details/computationaldis0000pemm|chapter=Permutations and combinations|first=Sriram V.|last=Pemmaraju|first2=Steven S.|last2=Skiena|publisher=Cambridge University Press|year=2003|isbn=978-0-521-80686-2}}
* {{Cite book|ref=harv|title=Algorithms and Complexity|volume=1|first=J.S.|last=Vitter|first2=Ph.|last2=Flajolet|editor-first=Jan|editor-last=van Leeuwen|editor-link=Jan van Leeuwen|edition=2nd|publisher=Elsevier|year=1990|isbn=978-0-444-88071-0|chapter=Average-Case Analysis of Algorithms and Data Structures}}

{{پایان پانویس}}

=== خواندن بیشتر ===
* {{Cite journal|last=Margolius|first=Barbara H.|year=2001|title=Permutations with Inversions|journal=Journal of Integer Sequences|volume=4|ref=harv}}

=== اقدامات تبلیغاتی ===
* {{Cite journal|last=Mannila|first=Heikki|author-link=Heikki Mannila|year=1984|title=Measures of presortedness and optimal sorting algorithms|journal=Lecture Notes in Computer Science|volume=172|pages=324&ndash;336|doi=10.1007/3-540-13345-3_29|ref=harv}}
* {{Cite journal|last=Estivill-Castro|first=Vladimir|last2=Wood|first2=Derick|author-link2=Derick Wood|year=1989|title=A new measure of presortedness|journal=Information and Computation|volume=83|issue=1|pages=111&ndash;119|doi=10.1016/0890-5401(89)90050-3|ref=harv}}
* {{Cite journal|last=Skiena|first=Steven S.|year=1988|title=Encroaching lists as a measure of presortedness|journal=BIT|volume=28|issue=4|pages=755&ndash;784|doi=10.1007/bf01954897|ref=harv}}

[[رده:الگوریتم‌های مرتب‌سازی]]
[[رده:ترکیبیات]]
[[رده:جایگشت‌ها]]
[[رده:ریاضیات گسسته]]
[[رده:نظریه ترتیب]]