برنامه ی جایگشت با الگوریتم Lexicographical Permutation

 

در پست های قبل “الگوریتم جایگشت های یک رشته یا مجموعه با ++C” در مورد پیدا کردن جایگشت های یک آرایه صحبت کرده بودیم ولی آن روش روشی بازگشتی بود که از لحاظ سرعت و حافظه به دلیل ساختار بازگشتی اش کمی مشکل داشت ولی امروز الگوریتم سریعی تر را به شما معرفی می کنیم . همین طور این الگوریتم در صورت وجود عضو تکراری جایگشت تکراری ایجاد نمی کند.

یک از بهترین الگوریتم ها برای پیدا کردن جایگشت های المنت های یک آرایه استفاده از الگوریتم Next Lexicographical  Permutation است. این الگوریتم یک آرایه را می گیرد و جایگشت بعدی آن آرایه را می دهد بطوری که جایگشت جدید در بین همه جایگشت های ممکن اولین جایگشتی است که ظاهر می شود به طور مثال جایگشت های عدد هایی یک دو و سه به شکل زیر است:

۱ ۲ ۳

۱ ۳ ۲

۲ ۱ ۳

۲ ۳ ۱

۳ ۱ ۲

۳ ۲ ۱

   فرض کنید آرایه ما   ۳ ۱ ۲ است جایگشت بعدی آن ۱ ۳ ۲ است زیرا از بین جایگشت هایی که از ۲۱۳ بزرگ تر هستند ۲۳۱ کوچک ترین آن ها است .

الگوریتم جایگشت های بعدی Next Lexicographical Permutation هم جایگشت بعدی یک آرایه ورودی را تولید می کند.

الگوریتم آن به این صورت است (در تصویر زیر مراحل آمده است)‌:

۱ – ابتدا بزرگ ترین زیر suffix نزولی را از سمت راست آرایه پیدا می کنیم که در ورودی شکل زیر suffix مورد نظر ما

قسمت ۵۱۰ است به عضو قبل از شروع suffix که در شکل عدد دو است pivot می گویند.

۲ – در suffix کوچک ترین المنتی که از pivot بزرگ تر است را پیدا می کنیم و جای آن و pivot را عوض می کنیم.

۳ – با این کار کوچک ترین عضو ممکن را که باعث افزایش مقدار prefix می شد را به prefix منتقل کردیم. در این مرحله suffix را صعوی مرتب می کنیم ولی از آنجایی که خود suffix در حال حاضر نزولی است کافی است آن را برعکس کنیم به همین خاطر مرتب سازی نیازی نیست.

۴ – کوچک ترین عضو ممکن suffix را به prefix منتقل کردیم و suffix را صعودی مرتب کردیم در نتیجه آرایه ای که به دست آمده جایگشت بعدی آرایه ی اولیه است .

lexical permutation

کد پیدا کردن جایگشت بعدی ( Next Lexicographical  Permutation ) به زبان سی پلاس پلاس C++ :

 

تا اینجا جایگشت بعدی یک آرایه را توانستیم پیدا کنیم . همان طور که در تابع بالا می بینید در صورت وجود جایگشت بعدی آن را تولید می کند و مقدار true را بر می گرداند و صورتی که آرایه در حالت ماکزیمم خود باشد و جایگشت بعدی وجود نداشته باشد false را بر می گرداند. هزینه ی این الگوریتم (O(n است.

حالا می خواهیم یک تابع بنویسیم که تمام جایگشت های یک آرایه را تولید کند. برای این کار می گوییم ابتدا آرایه را سورت کن (اگر مرتب نکنیم آرایه را آنگاه جایگشت هایی که کوچک تر از حالت فعلی هستند  پیدا نمی شوند زیرا این الگوریتم جایگشت ها بعدی یک آرایه را می دهد نه جایگشت های قبلی) بعد از آن تا زمانی که تابع تولید جایگشت false نشده است جایگشت های بعدی آن را تولید کن. هزینه ی این الگوریتم  (!O(n* n است.

کد سی پلاس پلاس (c++) تولید همه ی جایگشت های (permutation) یک آرایه را همراه تست آن بر روی دو آرایه ی متفاوت را در زیر می بینید:

 

 

در تصویر زیر خروجی برنامه ی بالا را می بینید:result of permutation

اگر کد این برنامه را با زبانی دیگر نوشته اید آن را برایمان ارسال کنید تا به این پست اضافه اش کنیم.

 

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)

One comment

  • به خاطر توانایی شما در ارایه این مطالب تبریک میگویم. فکر نمی کردم یک سایت فارسی پیدا شود که در این سطح حرفه ای زبان ++C را آموزش دهد.

Leave a Reply

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