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

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

Input : str[] = "acb"
Output : Rank = 2

Input : str[] = "string"
Output : Rank = 598

Input : str[] = "cba"
Output : Rank = 6

برای ساده‌تر شدن مسأله، فرض می‌شود که رشته هیچ کاراکتر تکراری ندارد. یک راهکار ساده مقداردهی اولیه به امتیاز است. در ابتدا، مقدار ۱ به امتیاز (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

خروجی قطعه کدهای بالا به صورت زیر است.

598

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

فیلم آموزش رشته و متن در برنامه نویسی پایتون (رایگان) در فرادرس

کلیک کنید

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

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

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

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

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

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

خروجی قطعه کدهای بالا به صورت زیر است.

598

برنامه‌های بالا برای رشته‌های حاوی کاراکتر تکراری کار نمی‌کنند. برای اینکه برنامه برای کاراکترهای تکراری نیز کار کند، باید همه کاراکترهایی که کوچک‌تر و مساوی هستند پیدا و عملیات بیان شده در بالا، در اینجا نیز انجام شود.

فیلم مجموعه آموزش برنامه نویسی پایتون Python – مقدماتی تا پیشرفته در فرادرس

کلیک کنید

این بار، امتیاز محاسبه شده باید بر !p تقسیم شود. P تعداد وقوع کاراکترهای تکراری است.

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

• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• آموزش ساختمان داده‌ها
• مجموعه آموزش‌های ساختمان داده و طراحی الگوریتم
• یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
• الگوریتم بازی مار و پله همراه با کد — به زبان ساده
• حل مساله n وزیر با الگوریتم پس‌گرد (Backtracking) — به زبان ساده

^^