تبلیغات


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

اشتراک گذاری
Share on FacebookTweet about this on TwitterShare on Google+Share on LinkedInPin on PinterestPrint this pageEmail this to someone

Permutation

قبل از هر چیزی تعریفی دقیقی از جایگشت ها (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 )  ::

 

 


تبلیغات:

۴ دیدگاه

  • جالبه اما سخت

  • سلام

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

    • در تعریف جایگشت 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 است.

نظر خود را بنویسید.

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *