Combinatorial algorithm

[Ehsan MNZ]

دوستان الگوریتم ترکیبیات دار، یه جوری ارائه بدین

که یکشنبه و سه شنبه تموم شه، نکشه مارو بعدا باز دانشگاه

[Mojtaba Javan]

این الگوریتم جزوه ی ترکیبیاتی اشتباس : nextCatala(a, n)
الگوریتمیه که خود استاد گفته و تو کتاب نی
رفتم باهاش صحبت کردم گفت آره اشتباهه مث اینکه، درستش کنید

Algorithm nextCatalan(a, n)
begin
i = 2n;
m = n;
while ((ai != 0) or ((i = 2m - 1) and (i > 0)))
begin
if (ai = 0)
m = m - 1;
i = i - 1;
end
if (i = 0)
return "undefined"
ai = 1;
for j = i + 1 to i + n - m + 1 //Here
ai = 0;
for j = i + n - m + 2 to 2n //Here
ai = 1;
return a;
end

[Pegah Moradi]

are eshtebah bud, dastet dard nakone :)

2012/6/5 Mojtaba Javan <javan....@gmail.com>

[Mojtaba Javan]

متن زیر رو توی نوت پد کپی کنید

در مورد الگوریتم catalanNext یه نفر سوال داشت، گفتم توضیحشو بذارم اینجا،
مث بیشتر الگوریتم های successor از سمت راست میریم به سمت چپ، به هر 1 که رسیدیم باید ردش کنیم، چون یک رو نمیشه اضافه کرد(ارقام فقط 0 و 1)
اگه به صفر رسیدیم، و اگه توی مکان 2m-1 بودیم ازش رد می شیم، حالا چرا؟

نکته اینجاس: مشخصه که اگه انتهای رشته مون به صورت 01 استار باشه، یعنی ...0101010101(آخری حتما یکه) هیچ صفری رو توی اون بازه نمیشه اضافه کرد. پس باید کلیه 01 های

متوالی رو از انتهای رشته رد کنیم. حالا فرض کنید m تعداد صفرهایی باشه که می تونیم بهشون برسیم و امیدوار باشیم که بتونیم اضافه کنیم. توی شروع الگوریتم m همون nه. حالا اگه

انتهای رشته 01 باشه پس m باید کم بشه. اگه مجددا یه 01 دیگه داشته باشیم مجددا باید از m کم بشه چون این صفر رو هم نمیشه اضافه کرد. و...(این صفرها توی مکان 2m-1 هستن) تا جایی که انتهای رشته مون از حالت 01

استار خارج بشه. یعنی مثلا به صورت ...110101010101 باشه. مشخصه که قبل از 01 استار حتما باید 2 تا 1 باشه. 01 که نمی تونه باشه، 10 هم نمی تونه باشه چون از حالت کاتالان

خارج میشه، 00 هم همینطور. حلقه ی while میاد 01 استار رو رد می کنه و هر چی یک هم هست رد می کنه تا به یه صفر برسه. اگه کل رشته 01 استار بود که "تعریف نشده برمی

گردونه". در غیر این صورت اون صفر رو اضافه می کنیم(یک می کنیم). چون قاموسی می خوایم تولید کنیم پس بعد از یک کردن باید به تعداد صفرهایی که جلوی اون مکان هست صفر

بذاریم که میشه n-m+1(بعلاوه ی یک به خاطر اینه که صفر فعلی رو یک کردیم). بقیش رو هم یک می کنیم.

سوالی هست بگید