الگوریتم گروه بندی کلمات مقلوب در جاوا اسکریپت — راهنمای کاربردی

در این مقاله قصد داریم به بررسی یک الگوریتم جاوا اسکریپت بپردازیم که اقدام به گروه بندی کلمات مقلوب در یک آرایه می‌کند. بدین ترتیب آرایه‌ای از کلمات در جاوا اسکریپت ارائه می‌شود که الگوریتم موردنظر باید کلماتی را که مقلوب هم هستند، یعنی با جایگشت حروف همدیگر تشکیل یافته‌اند را در گروه‌های یکسانی قرار دهد. همه حروف به صورت «حروف کوچک» (Lowercase) هستند و ترتیب ورودی‌ها و خروجی‌ها اهمیتی ندارد. برای درک بهتر این مسئله به تصویر زیر توجه کنید:

شاید فکر کنید الگوریتم حل این مسئله باید کاملاً دشوار باشد، اما نتیجه کار شما را شگفت‌زده خواهد کرد.

تعریف مقلوب

شاید از قبل می‌دانید که تعریف مقلوب چیست، اما باید به برخی جزییات توجه ویژه‌ای داشته باشید. کلمه‌هایی که مقلوب همدیگر هستند دارای حروف یکسانی هستند.

فیلم آموزش جاوا اسکریپت JavaScript در فرادرس

کلیک کنید

به مثال زیر توجه کنید:

اگر در سبدی حروف a ،t و e را داشته باشیم، می‌توانیم کلمات ate ،eat و tea را با آن‌ها بسازیم. به طور مشابه اگر سبدی با حروف t ،a و n داشته باشیم، می‌توانیم کلمات nat و tan را با آن‌ها بسازیم.

این بدان معنی است که می‌توانیم این معما را با کاهش هر رشته به حروف آن و سپس چسباندن دسته‌های مختلف حروف به همدیگر و تشکیل رشته‌ای با دقیقاً همان حروف حل کنیم. اما شیوه اتصال حروف چگونه باید باشد؟ ما یک هش به صورت زیر ایجاد می‌کنیم:

خروجی چیزی مانند زیر خواهد بود:

1[“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]

برای این که آن را به یک هش تبدیل کنیم، باید مراحل زیر را طی کنیم.

ابتدا یک هش خالی بسازید:

1let hash = {}

سپس حروف را از هر رشته بردارید و آن‌ها را به یک کلید در هش جدید تبدیل کنید. برای این که برای مثال حروف کلمه ate را به دست آوریم، می‌توانیم از متد ()split جاوا اسکریپت استفاده کنیم:

اگر این کلید را به هش اضافه کنیم، می‌توانیم کاری کنیم که آن کلید به یک آرایه اشاره کند که مقلوب‌هایی با استفاده از آن حروف در آن قرار دارد. پس از ارزیابی eat چیزی مانند زیر داریم:

1hash = {
2     ["e", "a", "t"]: ["eat"]
3}

اما زمانی که کلمه tea را به دست آوردیم با مشکلی مواجه می‌شویم. این کلمه یک مقلوب eat است و از این رو باید آن را به همان آرایه اضافه کنیم. به جای آن زمانی که split اجرا می‌شود، همان حروف با ترتیب متفاوتی به دست می‌آید:

بنابراین به جای خروجی زیر:

1hash = {
2     ["e", "a", "t"]: ["eat", "tea" ]
3}

یک خروجی مانند زیر به دست می‌آید:

1hash = {
2     ["e", "a", "t"]: ["eat"],
3     ["t", "e", "a"]: ["tea"]
4}

برای اجتناب از این مشکل، پس از افراز رشته به صورت حروفی، می‌توانیم این حروف را به صورت الفبایی مرتب کنیم اگر این کار را برای هر دو کلمه tea و eat انجام دهیم در نهایت نتیجه زیر به دست می‌آید:

1hash = {
2     ["a", "e", "t"]: ["eat", "tea ]
3}

این دقیقاً همان چیزی است که می‌خواستیم.

راه‌اندازی یک حلقه برای ساختن هش

اکنون که می‌دانیم هش ما باید به چه شکلی باشد، یک حلقه می‌سازیم که هش را برای ما بسازد.

در خط 4 کد فوق از یک حلقه forEach استفاده کرده‌ایم که یک تابع callback می‌گیرد. این تابع callback به ما امکان می‌دهد که هر رشته را افراز کنیم، حروف را مرتب‌سازی نماییم و نتیجه را در متغیری به نام letters ذخیره کنیم.

در خط 7 از یک تابع سه‌گانه برای بررسی این که آیا هش از قبل یک کلید letters را دارد یا نه بهره می‌گیریم. اگر از قبل یکی از کلیدهای letters را نداشته باشد، کلید را اضافه می‌کنیم و رشته را در مقدار کلید قرار می‌دهیم:

1hash[letters].push(str)

اگر کلید وجود نداشته باشد، لازم نیست کلیدی را اضافه کنیم. به جای آن باید گام را فراتر گذاشته و رشته را به مقدار کلید اضافه کنیم. پس از این که حلقه ما ارزیابی همه رشته‌ها را به پایان رساند، هش ما به صورت زیر درمی‌آید:

گام آخر: قالب‌بندی خروجی با ()Object.keys

اکنون که هش را داریم، باید کاری کنیم که مانند خروجی مطلوب به نظر برسد:

ما به کلیدهای خود نیاز داریم. کافی است مقادیر خود را در یک آرایه قرار دهیم. اگر از Ruby استفاده می‌کنید، کافی است دستور زیر را اجرا کنید:

1hash.values()

در جاوا اسکریپت می‌توانیم همه کلیدهای خود را در یک آرایه قرار دهیم و سپس کلیدها را نگاشت می‌کنیم تا یک آرایه از همه مقادیر بازگشت دهیم.

در مجموع کد زیر را داریم:

برای دیدن پروژه به صورت زنده به این آدرس (+) مراجعه کنید. اینک کد ما عملکرد مناسبی دارد:

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

• مجموعه آموزش‌های برنامه‌‌نویسی
• آموزش JavaScript ES6 (جاوا اسکریپت)
• مجموعه آموزش‌های JavaScript (جاوا اسکریپت)
• جاوا اسکریپت چیست؟ — به زبان ساده
• کار با JSON در جاوا اسکریپت — راهنمای کاربردی

==