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

۱۹۲ بازدید
آخرین به‌روزرسانی: ۷ شهریور ۱۴۰۲
زمان مطالعه: ۳ دقیقه
دانلود PDF مقاله
الگوریتم گروه بندی کلمات مقلوب در جاوا اسکریپت — راهنمای کاربردیالگوریتم گروه بندی کلمات مقلوب در جاوا اسکریپت — راهنمای کاربردی

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

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

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

تعریف مقلوب

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

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

اگر در سبدی حروف 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-in-plain-english
نظر شما چیست؟

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