تکرار بیش از جایگشت

جایگشتی به طول n مجموعه ای مرتب شده بدون تکرار اعداد 1، 2، ...، n است. برای مثال، [3، 1، 2] و [5، 4، 3، 2، 1] جایگشت هستند، اما [1، 2، 1، 3] و [1، 2، 4] جایگشت نیستند.

اگر کار به این واقعیت کاهش یابد که لازم است روی همه جایگشت‌های طول n تکرار شود، می‌توانید از مکانیزم مناسبی در C ++ استفاده کنید که به آن "next_permutation" می‌گویند.

می‌توانید در مستندات اطلاعات بیشتری در مورد آن بخوانید، اما نکته اینجاست که این تابع آرایه ارسال شده را تغییر می‌دهد. به جایگشت بعدی به ترتیب واژگانی (که عموماً مشخص است و نام آن مشخص است).

برای استفاده از next_permutation، باید کتابخانه الگوریتم را اضافه کنید (یعنی در ابتدای برنامه #include <algorithm> بنویسید)

مثال ها: vector arr; arr = { 1, 2, 3 }; // آرایه [1، 2، 3] است next_permutation(arr.begin()، arr.end()); // کل آرایه را به تابع منتقل کنید // آرایه اکنون [1، 3، 2] است arr = { 2, 3, 1 }; // آرایه [2، 3، 1] است next_permutation(arr.begin()، arr.end()); // کل آرایه را به تابع منتقل کنید // آرایه اکنون [3، 1، 2] است next_permutation(arr.begin() + 1, arr.begin() + 3); // می توان یک تابع را به بخشی از یک آرایه اعمال کرد، اما در عمل به ندرت به این مورد نیاز است // آرایه اکنون [3، 2، 1] است
در این حالت، تابع دارای یک مقدار بازگشتی بولی است که اگر جایگشت بعدی ایجاد شده باشد درست است و اگر جایگشت بعدی وجود نداشته باشد نادرست است (موردی که حداکثر جایگشت به ترتیب واژگانی به تابع منتقل می شود).
این امکان استفاده از تابع را در یک حلقه فراهم می کند، که به ما امکان می دهد روی همه جایگشت ها به طور همزمان تکرار کنیم. به دلیل نمایه سازی 0، در عمل اغلب کار با جایگشت اعداد از 0 تا n - 1 راحت تر است، اگرچه یک جایگشت به طور رسمی شامل اعداد 1 تا n است. اما خوشبختانه، این منجر به همپوشانی اضافی در کد نمی شود، زیرا تابع next_permutation با جایگشت های 0-index شده سازگار است (و حتی عناصر تکراری در یک آرایه، اما شما می توانید بیشتر به تنهایی بیابید).

به طور کلی، کد تکرار روی همه جایگشت ها به این صورت است:   intn; // اندازه جایگشت vectorperm(n); // perm مخفف "جایگشت" است، یعنی. "جایگزینی" برای (int i = 0; i < n; i++) perm[i] = i; // جایگشت اولیه 0، 1، ...، n - 1 را مقداردهی کنید انجام دادن { // در داخل حلقه، جایگشت فعلی را پردازش می کنیم } while (next_permutation(perm.begin()، perm.end())); // اگر جایگشت بعدی وجود ندارد، حلقه را پایان دهید

این کد در O(n! * f(n)) اجرا می شود، که در آن f(n) زمانی است که برای پردازش یک جایگشت خاص طول می کشد.