الگوریتم جایگشت های رشته یا مجموعه با ++C
قبل از هر چیزی تعریفی دقیقی از جایگشت ها (permutation ) را باید بدانیم که در زیر ارائه شده است.
یک جایگشت (خطی) عبارت است ازهرترتیب قرار گرفتن کلکسیونی از اشیا ( بصورت خطی) بوجود می آید.
در اینجا به کلمه ی ” خطی ” دقت شود زیرا جایگشت دیگری نیز به نام جایگشت دوری داریم که در آن اشیا بصورت دایره ای قرار میگیرند و کلمه ی ” خطی ” در تقابل با مفهوم جایگشت دوری آمده است. الگوریتم این برنامه را با مثال توضیح میدهیم.
جایگشتهای مجموعه ی {a,b,c,d,e} برابرند با اجتماع مجموعه های زیر:
a و جایگشتهای مجموعه ی {b,c,d,e}
b و جایگشتهای مجموعه ی{a,c,d,e}
c و جایگشتهای مجموعه ی {a,b,d,e}
d و جایگشتهای مجموعه ی {a,b,c,e}
e و جایگشتهای مجموعه ی {a,b,c,d}
پس در هر مرحله یک عضو از مجموعه (در این جا یک کاراکتر از کل رشته ) را انتخاب میکنیم و با جایگشت بقیه ی اعضا در نظر میگیریم اما از آنجایی که برای تمام اعضای مجموعه این کار باید انجام شود این کار با یک حلقه ی for و تعویض هر عضو مجموعه با اولین عضو انجام میدهیم.
تابع بازگشتی برای انجام این الگوریتم بصوریت بازگشتی بوده و ۳ آرگومان دارد اولی خود رشته (مجموعه) است , دومی کاراکتری (عضوی از مجموعه) است که در هر مرحله
جایش را با کارکتر های (اعضای) بعد از خود عوض میکند و هنگام فراخونی اولیه تابع در این آرگومان صفر قرار میگیرد و آرگومان سوم ایندکس آخرین کاراکتر (عضو) است چون لازم است که در چه مرحله ای به کاراکتر (عضو) آخر برای فراخوانی دوباره میرسیم.
و این هم کد برنامه جایگشت ها ی (permutation ) یک مجموعه با زبان برنامه نویسی سی پلاس پلاس ( ++C ) ::
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | #include <iostream> #include <string> using namespace std; void per(string s,int k,int n) { if(k==n) { cout<<s<<endl; } else { for(int i=k;i<=n;i++) { char c=s[i]; s[i]=s[k]; s[k]=c; per(s,k+1,n); } } } int main(void) { string s; cout<<"\t\t\t\tPermutation"<<endl<<endl; cout<<"Enter the string: "; cin>>s; per(s,0,s.size()-1); cin.get(); return 0; } |
جالبه اما سخت
چند تا مثال بزنید و روی کاغذ با دست انجامش بدهید . راحت متوجه خواهید شد
سلام
تو کاغذ هم راحت نیست که
خیلی سخته
سلام
من نفهمیدم چه طوری کار می کنه. انگار شعبده بازیه! یه کار کن بفهمم چی شد! عکسی نموداری فیلمی چیزی
در تعریف جایگشت n داریم !(n!=n*(n-1 یعنی
۱- (دلیل وجود حلقه ی for) عضو اول میتواند n حالت داشته باشد که ما این کار را با جابجا کردن عضو اول به ترتیب با تمامی اعضا انجام میدهیم و در مرحله ی اول عضو اول با خودش جابجا میشود
۲-بعد از مشخص شدن عضو اول در جایگشت, دوباره فراخوانی تابع جایگشت برای بقیه ی اعضا (که تعداد یکی کمتر است) انجام میشود که در اینجا از (per(s,k+1,n استفاده شده است تابع (per(s,x,y در اینجا جایگشت های رشته (مجموعه) s را از x تا y نشان میدهد, بعد از مشخص شدن عضو اول (همان x) فراخوانی مجدد تابع بصورت (per(s,x+1,y است.