سلام.
بهتر بود توی قسمت الگوریتم سوالتون رو مطرح می کردین.
یک روش استفاده از روش backtrack هست که به صورت الفبایی چاپ می کنه، یک روش استفاده از شمارش باینری هست، اگر هم بخاهیم اول زیر مجموعه های تک عضوی بعد دو عضوب بعد...رو چاپ کنیم باید در یک حلقه مثلا i که از 1 تا تعداد اعداد یعنی n پیش می ره در هر گامش ترکیبات i شی از n شی رو بدست بیاریم:
در مورد روش باینری قبلا بحث شده پس من روش اول رو توضیح می دم.
backtrack:
الگوریتم های بک ترک عموما به شکل زیر هستند و برای مسائل زیادی کار برد دارند.
initialize;
repeat
if current partial solution is extendable then extend else reduce;
if current solution is acceptable then report it;
until search is over
حالت extend زمانی اتفاق می افتد که ما یک قدم به جلو برویم (الان مثالشو می بینید)، و حالت reduce زمانی اتفاق می افتد که ما نتوانیم به جلو برویم.
برای اینکه با این الگورم مجموعه زیر مجموعه ها رو بدست بیاریم به روش زیر عمل می کنیم.
فرض کنید 5 تا عضو داریم. 1و2و3و4و5. (می تونید هر کدوم رو اندیس فرض کنید اینطوری عمومیت مساله حفض میشه یعنی هر جا گفتیم 5 رو چاپ کن تو آرایه بیاییم عنصرو 5 ام رو چاپ کنیم.). زیر مجموعه هاشو به طور الفبایی مرتب می کنیم. (انگار یه سری اسم رو به تربیت الفبا مرتب می کنیم):
1 12 123 1234 12345
1235
124 1245
125
13 134 1345
135
14 145
15
2 23 234 2345
235
24 245
25
3 34 345
35
4 45
5
الگوریم ما باید بیاد اینها رو یکی یکی چاپ کنه.
حالت extend یا گسترش زمانی اتفاق می افته که در یه سطر پیش می ریم. یعنی آخرین عضو زیر مجموعه کوچکتر از 5 باشه.
حالت reduce یا کاهش زمانی اتفاق می افته که یک پایین بیاییم. یعنی آخرین عضو زیر مجموعه برابر با 5 بشه.
الگوریتم:
read( n); r ← 0; x[r] ← 0;
repeat
if x[r]<n then extend else reduce;
print out x[1], x[2], . . . , x[r]
until x[1] = n
extend ≡ {x[r+1] ← x[r] + 1; r ← r + 1}
reduce ≡ {r ← r − 1; x[r] ← x[r] + 1}