الگوریتم هیپ
الگوریتم هیپ یک الگوریتم برای تولید تمامی جایگشت‌های ممکن برای یک طول داده شده‌است. این الگوریتم اولین بار توسط بی. ار. هیپ در سال ۱۹۶۳ پیشنهاد داده شد.[۱] این الگوریتم هر جایگشتی را از جایگشت قبلی با انتخاب یک جفت از عناصر برای جابجایی استفاده می‌کند. در بازبینی سال ۱۹۷۷ الگوریتم‌های تولید جایگشت، رابرت سدویک به این نتیجه رسیده بود که این الگوریتم، الگوریتم بهینه برای تولید جایگشت‌ها با کامپیوتر در آن زمان بوده‌است.[۲]
جزئیات الگوریتم[ویرایش]
یک جایگشت که دارای N کاراکتر مختلف می‌باشد را تصور کنید. هیپ در هر مرحله روشی نظام‌مند برای جابه‌جا کردن یک جفت از عنصرها پیدا می‌کند، برای دقیقاً یک‌بار تولید کردن هر جایگشت ممکن. بیایید الگوریتم هیپ را به صورت بازگشتی تشریح کنیم. در ابتدا یک شمارنده؛ i تا ۱؛ را می‌گیریم. حال مراحل زیر را به صورت متوالی انجام می‌دهیم، تا زمانی که i بزرگ‌تر از N باشد. ما از الگوریتم برای تولید !(N − 1) جایگشت ممکن برای N − ۱ کاراکتر اول و مجاور کردن (اضافه کردن) کاراکتر آخر به هرکدام از جایگشت ها؛ استفاده می‌کنیم. با این روش تمام جایگشت‌هایی که با کاراکتر آخر تمام می‌شود را تولید می‌کنیم. سپس اگر N فرد بود، عنصر اول و آخر را جابه‌جا می‌کنیم. در همین حین؛ اگر i زوج بود؛ عنصر iام را می‌توانیم با عنصر آخر جابه‌جا کنیم (در تکرار برای دفعه اول تفاوتی بین زوج و فرد وجود ندارد). یکی به شمارنده i اضلفه می‌کنیم و این روند را تکرا می‌نمائیم. در هر تکرار، در هر مرحله الگوریتم تمام جایگشت‌های ممکن را که با کاراکتری که اخیراً به محل «آخرین عنصر» منتقل شده؛ تمام می‌شود را می‌سازد. شبه کد زیر تمام جایگشت‌های ممکن برای یک آرایه به طول N را تولید می‌کند:
procedure generate(N: integer, data: array of any):
if N = 1 then
output(data)
else
for c := 1; c <= N; c += 1 do
generate(N - 1, data)
swap(data[if N is odd then 1 else c], data[N])
همچنین می‌توان الگوریتم را به صورت غیر بازگشتی هم نوشت..[۳]
پانویس[ویرایش]
- ↑ Heap, B. R. (1963). "Permutations by Interchanges" (PDF). The Computer Journal. 6 (3): 293–4. doi:10.1093/comjnl/6.3.293.
- ↑ Sedgewick, Robert (1977). "Permutation Generation Methods". ACM Computing Surveys. 9 (2): 137–164. doi:10.1145/356689.356692. ISSN 0360-0300.
- ↑ Sedgewick, Robert. "a talk on Permutation Generation Algorithms" (PDF).