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

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 )  ::

 

 

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)

۳ comments

  • Pingback: برنامه ی جایگشت با الگوریتم Lexicographical Permutation | برنامه نویسی و الگوریتم

  • سلام

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

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

Leave a Reply

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