سورس کد الگوریتم هیپ به زبان سی پلاس پلاس

الگوریتم هیپ یک الگوریتم برای تولید تمامی جایگشت‌های ممکن برای یک طول داده شده است.این الگوریتم اولین بار توسط بی. ار. هیپ در سال ۱۹۶۳ پیشنهاد داده شد.[۱] این الگوریتم هر جایگشتی را از جایگشت قبلی با انتخاب یک جفت از عناصر برای جابجایی استفاده می‌کند.در بازبینی سال ۱۹۷۷ الگوریتم‌های تولید جایگشت، رابرت سدویک به این نتیجه رسیده بود که این الگوریتم، الگوریتم بهینه برای تولید جایگشت‌ها با کامپیوتر در آن زمان بوده است.[۲];

یک جایگشت که دارای N کاراکتر مختلف می‌باشد را تصور کنید.

الگوریتم هیپ در هر مرحله روشی نظام‌مند برای جابه‌جا کردن یک جفت از عنصرها پیدا می‌کند،

برای دقیقاً یک‌بار تولید کردن هر جایگشت ممکن بیایید الگوریتم هیپ را بصورت بازگشتی تشریح کنیم.

در ابتدا یک شمارنده؛ i تا ۱؛ را می‌گیریم. حال مراحل زیر را بصورت متوالی انجام می‌دهیم،

  1. تا زمانی که i بزرگ‌تر از N باشد.

  2.  الگوریتم هیپ برای تولید !(N − 1) جایگشت ممکن برای N − ۱ کاراکتر اول و مجاور کردن (اضافه کردن) کاراکتر آخر به هرکدام از جایگشت ها؛ استفاده می‌کنیم.

  3. با این روش تمام جایگشت‌هایی که با کاراکتر آخر تمام می‌شود را تولید می‌کنیم.

  4. سپس اگر N فرد بود، عنصر اول و آخر را جابه‌جا می‌کنیم. در همین حین؛ اگر i زوج بود؛ عنصر iام را می‌توانیم با عنصر آخر جابه‌جا کنیم (در تکرار برای دفعه اول تفاوتی بین زوج و فرد وجود ندارد).

  5. یکی به شمارنده i اضلفه می‌کنیم و این روند را تکرا می‌نمائیم.

  6. در هر تکرار، در هر مرحله الگوریتم تمام جایگشت‌های ممکن را که با کاراکتری که اخیراً به محل «آخرین عنصر» منتقل شده؛ تمام می‌شود را می‌سازد.

 

990 تومان – خرید

فیلم آموزشی بازدید : 300 بازدید ۵ دی, ۱۳۹۵ ۰