در این مطلب، روش محاسبه رتبه الفبایی یک رشته (Lexicographic Rank of a String) آموزش داده شده است. فرض می‌شود که یک رشته داده شده است. هدف پیدا کردن امتیاز رشته در میان همه جایگشت‌های آن است که به صورت الفبایی مرتب شده‌اند. برای مثال، امتیاز رشته «abc» برابر با ۱، «acb» برابر با ۲ و «cba» برابر با ۶ است. مثال زیر در این راستا قابل توجه است.

برای ساده‌تر شدن مسأله، فرض می‌شود که رشته هیچ کاراکتر تکراری ندارد. یک راهکار ساده مقداردهی اولیه به امتیاز است. در ابتدا، مقدار ۱ به امتیاز (Rank) داده می‌شود. سپس، همه جایگشت‌ها به ترتیب الفبایی تولید می‌شوند. پس از تولید جایگشت‌ها، اگر جایگشت تولید شده مشابه با رشته داده شده باشد، امتیاز بازگردانده می‌شود. در غیر این صورت، امتیاز، یکی افزایش پیدا می‌کند.

پیچیدگی زمانی این روش در بدترین حالت از درجه نمایی است. در ادامه، راهکار کارآمد برای حل این مساله بیان شده است. فرض می‌شود که رشته داده شده «STRING» است. در رشته ورودی، «S» اولین کاراکتر است. به طور کلی، ۶ کاراکتر در رشته وجود دارد و ۴ تای آن‌ها کوچک‌تر از S هستند. بنابراین، این امکان وجود دارد که !۵*۴ رشته کوچک‌تر وجود داشته باشد که در آن‌ها، اولین کاراکتر کوچک‌تر از S کوچک‌تر است. مثال‌هایی از این مورد، در ادامه آمده‌اند.

R X X X X X
I X X X X X
N X X X X X
G X X X X X

اکنون، S ثابت نگه داشته می‌شود و کوچک‌ترین رشته‌ها با شروع از S پیدا می‌شوند. فرایند مشابهی برای T انجام می‌شود. امتیاز این بار برابر با $$4*5! + 4*4! +…$$ است. اکنون T ثابت می‌شود و فرایند مشابهی برای R انجام می‌شود. امتیاز برابر با $$4*5! + 4*4! + 3*3! +…$$ است. پس از این گام، R ثابت می‌شود و فرایند برای I تکرار خواهد شد. امتیاز برابر با $$4*5! + 4*4! + 3*3! + 1*2! +…$$ است.

اکنون، I ثابت و فرایند برای N تکرار می‌شود. امتیاز برابر با $$4*5! + 4*4! + 3*3! + 1*2! + 1*1! +…$$ است. در این مرحله، N ثابت و فرایند مشابهی برای G انجام می‌شود. امتیاز برابر با $$4*5! + 4*4! + 3*3! + 1*2! + 1*1! + 0*0!$$ است.

امتیاز کامل برابر با $$4*5! + 4*4! + 3*3! + 1*2! + 1*1! + 0*0! = 597$$ است. باید توجه داشت که محاسبات بالا، تعداد رشته‌های کوچک‌تر را پیدا می‌کند. بنابراین، امتیاز رشته داده شده برابر با تعداد رشته‌های کوچک‌تر به علاوه ۱ است. امتیاز نهایی برابر با $$1 + 597 = 598$$ است.

در ادامه، پیاده‌سازی رویکرد بالا در زبان‌های برنامه‌نویسی گوناگون ارائه شده است.

کد محاسبه رتبه الفبایی یک رشته در C++‎

کد محاسبه رتبه الفبایی یک رشته در C

کد محاسبه رتبه الفبایی یک رشته در جاوا

کد محاسبه رتبه الفبایی یک رشته در پایتون

کد محاسبه رتبه الفبایی یک رشته در #C

کد محاسبه رتبه الفبایی یک رشته در PHP

خروجی قطعه کدهای بالا به صورت زیر است.
پیچیدگی زمانی راهکار بالا از درجه O(n2)‎ است. می‌توان پیچیدگی زمانی را با ساخت یک آرایه کمکی با سایز ۲۵۶ به O(n)‎ کاهش داد. قطعه کدهای زیر، با استفاده از این فضای کمکی پیاده‌سازی شده‌اند.

کد محاسبه رتبه الفبایی یک رشته با استفاده از آرایه کمکی در C++‎

کد محاسبه رتبه الفبایی یک رشته با استفاده از آرایه کمکی در C

کد محاسبه رتبه الفبایی یک رشته با استفاده از آرایه کمکی در جاوا

کد محاسبه رتبه الفبایی یک رشته با استفاده از آرایه کمکی در پایتون ۳

کد محاسبه رتبه الفبایی یک رشته با استفاده از آرایه کمکی در C#‎

کد محاسبه رتبه الفبایی یک رشته با استفاده از آرایه کمکی در PHP

خروجی قطعه کدهای بالا به صورت زیر است.
برنامه‌های بالا برای رشته‌های حاوی کاراکتر تکراری کار نمی‌کنند. برای اینکه برنامه برای کاراکترهای تکراری نیز کار کند، باید همه کاراکترهایی که کوچک‌تر و مساوی هستند پیدا و عملیات بیان شده در بالا، در اینجا نیز انجام شود. این بار، امتیاز محاسبه شده باید بر !p تقسیم شود. P تعداد وقوع کاراکترهای تکراری است.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

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

آیا این مطلب برای شما مفید بود؟

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *