الگوریتم جایگشت های رشته یا مجموعه با ++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 ) ::

#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;
}

#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;

}

الگوریتم ها و هوش مصنوعی, تقسیم و حل - Divide and conquer, سی پلاس پلاس - ++C, عقبگرد - backtracking

۴ نظر

Nima

۱۳۹۶/۰۳/۱۳ در ۲۰:۰۲

جالبه اما سخت

پاسخ
- farhad dalirani
  
  ۱۳۹۶/۰۳/۱۹ در ۲۳:۱۸
  
  چند تا مثال بزنید و روی کاغذ با دست انجامش بدهید . راحت متوجه خواهید شد
  
  پاسخ
rio

۱۳۹۳/۰۵/۰۵ در ۱۷:۰۶

سلام

من نفهمیدم چه طوری کار می کنه. انگار شعبده بازیه! یه کار کن بفهمم چی شد! عکسی نموداری فیلمی چیزی

پاسخ
- Reshad Shokri
  
  ۱۳۹۳/۰۵/۰۷ در ۲۲:۰۳
  
  در تعریف جایگشت 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 است.
  
  پاسخ

الگوریتم جایگشت های رشته یا مجموعه با ++C

مطالب آموزنده مشابه:

۴ نظر

نظرتان را برای ما بنویسید لغو پاسخ