دنباله ای که دو عنصر آن از نظم عادی و طبیعی خود پیروی نمی کنند و از این قاعده خارج هستند From Wikipedia, the free encyclopedia
در علوم کامپیوتر و ریاضیات گسسته، دنبالهای وارونگی دارد که دو عنصر آن از نظم عادی خود خارج هستند. تعداد وارونگیهای یک جایگشت به ما نشان میدهد که آن جایگشت تا چهحد از نظم طبیعی(همان ترتیب عادی)خود خارج است.
را جایگشتی دلخواه درنظربگیرید. اگر در جایگشت ، و باشد، آنگاه جفت اندیس [1][2] یا جفت عنصر [3][4][5]، یک وارونگی از جایگشت نامیده میشوند.
وارونگی معمولاً برای جایگشتها تعریف میشود، ولی امکان دارد برای دنباله نیز تعریف شود:
را یک دنباله (یا جایگشت Multi Set [6])درنظر بگیرید. اگر و باشد، به دو اندیس [6] [7] یا دو عنصر [8] وارونگی گفته میشود.
برای دنبالهها، وارونگیها طبق تعریف مبتنی بر عنصر، یکتا نیستند، زیرا امکان دارد جفت اندیسهای متفاوت مقادیر یکسانی داشته باشند.
مجموعه وارونگی، مجموعه همه وارونگیها است. مجموعهٔ وارونگی یک جایگشت با توجه به تعریف مبتنی بر مکان، همان است که از معکوس مجموعه وارونگی جایگشت با توجه به تعریف مبتنی بر عنصر به دست میآید و بالعکس، [9] تنها با رد و بدل عناصر از جفتها.
عدد وارونگی شاخص بارز مجموعه وارونگی است. این یک اندازهگیری رایج از مرتبسازی یک جایگشت [5] یا دنباله است. [8]
عدد وارونگی تعداد برخوردها در نمودار پیکانی جایگشت است، [9] فاصله Kendall tau آن، از جایگاه اصلی و جمع هر یک از بردارهای مربوط به وارونگی که در زیر تعریف شدهاست.
مهم نیست که از تعریف مبتنی بر مکان یا مبتنی بر عنصر وارونگی برای تعریف عدد وارونگی استفاده شود، زیرا یک جایگشت و معکوس آن دارای تعداد وارونگیهای یکسانی هستند.
دیگر اندازهگیریهای (پیش-) مرتبسازی شامل حداقل تعداد عناصری که میتوانند از دنباله حذف شوند تا یک دنباله کاملاً مرتب حاصل شود، تعداد و طول «اجراهای» مرتب شده در داخل دنباله، Spearman Footrule (مجموع فاصلههای هر عنصر از مکان قرارگیری آن پس از مرتبسازی) و کمترین تعداد جابجایی مورد نیاز برای مرتبسازی دنباله است. [10] الگوریتمهای مرتبسازی مقایسه استاندارد میتوانند برای محاسبه تعداد وارونگی در زمان O(n log n) سازگار شوند.
سه بردار مشابه در حال استفاده هستند که وارونگیهای یک جایگشت را در یک بردار خلاصه میکنند که آن جایگشت را بهطور یکتایی مشخص میکند. آنها معمولاً بردار وارونگی یا کد لیمر نامیده میشوند. (لیستی از منابع در اینجا یافت میشود )
این مقاله از اصطلاح بردار وارونگی استفاده میکند () مثل ولفرام[11]. دو بردار باقی مانده گاهی بردار وارونگی چپ و راست نامیده میشوند، اما برای پیشگیری از اشتباه گرفتن با بردار وارونگی این مقاله آنها را تعداد معکوس چپ () و تعداد معکوس راست ()مینامد.
بعنوان عدد فاکتوریل تعبیر شدهاست. تعداد وارونگی سمت چپ جایگشتها، شاخصreverse colexicographic[12] و تعداد وارونگی سمت راست آنها، شاخص lexicographic را در اختیار ما قرار میدهد.
بردار وارونگی () : با توجه به تعریف مبتنی بر عنصر، همان تعداد وارونگیهایی است که مؤلفه کوچکتر (سمت راست) آنها است. [3]
تعداد عناصر موجود در است که از بزرگترند و قبل از قرار دارند.
تعداد معکوس سمت چپ () : با تعریف مبتنی به مکان، تعداد وارونگیهایی است که مؤلفه بزرگتر (راست) آنها است.
تعداد عناصر موجود در بزرگتر از قبل از .
تعداد معکوس سمت راست () : (اغلب به نام کد لیمر خوانده میشود)
با تعریف مبتنی بر مکان، تعداد وارونگیهایی است که مؤلفه کوچکتر (سمت چپ) آنها است.
تعداد عناصری است که در قرار دارند، از کوچکترند و بعد از قرار گرفتهاند.
و ، هردو را میتوان به کمک نمودار روته یافت؛ که یک ماتریس جابگشت، با ۱هایی است که توسط نقاط نشان داده میشوند و یک وارونگی (که اغلب توسط یک صلیب نمایش داده میشود) در هر موقعیتی که دارای نقطه ای در سمت راست و زیر آن است، مشخص میشود. مجموع وارونگیهای موجود در ردیف i ام نمودار روته است، در حالی که مجموع وارونگیهای موجود در ستون i ام نمودار روته است. ماتریس جایگشت معکوس، ترانهاده شده ماتریس اولیه است بنابراین مؤلفه یک جایگشت، مؤلفه معکوس آن میباشد و بلعکس.
جدول مرتبسازی زیر ۲۴ جایگشت حاصل از چهار عنصر با مجموعههای وارونگی مکان محور آنها، بردارهای مربوط به وارونگی و اعداد وارونگی را نشان میدهد. (ستونهای کوچک بازتاب ستونهایی هستند که در کنار آنها قرار دارند و میتوان از آنها برای مرتب کردنشان به ترتیب colexicographic استفاده کرد)
مشاهده میشود که و همیشه ارقام مشابهی دارند و این و هر دو مرتبط به مجموعه وارونگی مکان محور هستند. عناصر غیرمستقیم جمع نمودارهای نزولی مثلث نمایش داده شده و همین موارد از جمع نمودارهای صعودی آن هستند. (جفتهای موجود در نمودارهای نزولی دارای مؤلفههای راست ۲، ۳، ۴ مشترک هستند، در حالی که جفتهای موجود در نمودارهای صعودی دارای مؤلفههای چپ ۱، ۲، ۳ مشترک هستند). )
ترتیب پیش فرض جدول، ترتیب reverse colexicographic جایگشت است، که همان ترتیب colexicographic است. ترتیب lexicographic ، همان ترتیب lexicographic است.
در ریاضیات ترتیب lexicographic یا (ترتیب الفبایی) نوعی سازماندهی است که در آن کلمات بهترتیب الفبایی براساس ترتیب الفبایی حروف تشکیل دهندهی آنها مرتب میشوند. همچنین اگر طول دو کلمه باهم متفاوت بود کلمه با طول کمتر اولویت پیدا میکند. این نوع سازماندهی بهصورت کلی در مورد دنبالههایی بهکار میروند که
اعضای آنها متناهی باشند و از یک جامعه خاص و متناهی انتخاب شوند که به این جامعه الفبا گفته میشود. در مباحث علوم کامپیوتر چنین دنبالههایی بهاصطلاح رشتهای از کاراکترها یا ارقام نامیده میشوند. بهطوز مثال با این ترتیب داریم : 25 < 34
این ترتیب بهطریقی در مقابل ترتیب lexicographic قرار دارد. چون در ترتیب lexicographic بهدنبال اولین رقم از سمت چپ میباشیم که با رقم در همین جایگاه از یک دنباله
دیگر متفاوت باشد اما در ترتیب colexicographic، ما بهدنبال آخرین رقم از سمت چپ (اولین رقم از سمت راست) میباشیم که با رقم موجود در همین جایگاه از دنباله دیگر
متفاوت باشد. بهطور مثال با ترتیب colexicographic داریم : 34 < 25
مجموعه جایگشتهای n مورد، میتواند ساختار یک دستورالعمل جزئی را بدهد، که ترتیب ضعیف جایگشتها نامیده میشود، و یک شبکه تشکیل میدهد.
نمودار هسه مجموعههای وارونگی که توسط رابطه زیرمجموعه ای مرتب شده، اسکلت یک permutohedron را تشکیل میدهد.
اگر یک جایگشت به هر مجموعه وارونگی، با استفاده از تعریف مبتنی بر مکان اختصاص داده شود، نظم حاصل از جایگشتها، همان permutohedron است، که در آن یک لبه مربوط به مبادله دو عنصر با مقادیر متوالی است. این ترتیب ضعیف جایگشت است. اگر یک جایگشت به هر مجموعه وارونگی با استفاده از تعریف مبتنی بر مکان تخصیص داده شود، نظم حاصل یک گراف Cayley خواهد بود، که در آن یک لبه مربوط به تعویض دو عنصر موجود در مکانهای متوالی است. این نمودار Cayley از یک گروه متقارن، مشابه با permutohedron است، اما با جایگزینی هر جایگشت با معکوس آن حاصل میشود.
توالیهای موجود در OEIS :
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.