افرازهای عدد صحیح
تعریف، تولید و افرازهای مقید
امیرحسین محمودی
تعریف، تولید و افرازهای مقید
امیرحسین محمودی
افرازِ یک عدد صحیح مثبت، نوشتن آن بهصورت مجموع اجزای صحیح مثبت، بدون توجه به ترتیب است.
نماد m: مجموعِ موردنظر
نماد N: تعداد اجزا
نماد aᵢ: اندازهٔ جزء شمارهٔ i
اجزا را میتوان با هر ترتیبی نوشت.
هر جزء را مانند ارزش یک سکه در نظر بگیرید.
ترتیب مهم نیست؛ اجزای برابر و افراز تکجزئی نیز مجازند.
افراز تکجزئیِ ۶ نیز یک پاسخ است؛ سکهها اجزا را نشان میدهند.
یک افراز؛ جابهجایی اجزا یا سکهها پاسخ تازه نمیسازد.
اگر ترتیب اجزا را ثبت کنیم، دو ترکیب مرتب متفاوت داریم.
فرم استاندارد یعنی نوشتن اجزای افراز بهترتیب غیرصعودی؛ از بزرگترین به کوچکترین، با امکان تکرار.
هر جزء، بزرگتر یا مساوی جزء بعدی است.
اجزای برابر مجازند؛ ترتیب، اکیداً نزولی نیست.
مرتبسازی غیرصعودی
فقط ترتیب نوشتن عوض شده است، نه خود افراز. مولد هنگام ساخت پاسخها همین فرم را حفظ میکند.
تابع P(m)، تعداد افرازهای عدد m است.
رشد از هر چندجملهای ثابت سریعتر است؛ اما نسبت به مجموع، زیرنمایی است.
نماد ∼ یعنی نسبت دو طرف با بزرگشدن m به ۱ میل میکند؛ این برابری دقیق نیست.
برای P(m) فرمول بستهٔ سادهای با توابع ابتدایی شناخته نشده است؛ اما رشد مجانبی آن معلوم است و در بالا آمده است. محاسبهٔ دقیق تعداد همچنان ممکن است.
هدف: برای عدد صحیح مثبت m، همهٔ افرازهای آن را در فرم استاندارد و هرکدام دقیقاً یک بار تولید کنیم.
۱. هر مقدار مجاز برای جزء بعدی را امتحان میکنیم.
۲. مجموع باقیمانده را بهصورت بازگشتی افراز میکنیم.
۳. جزءهای بعدی را از جزء فعلی بزرگتر نمیگیریم تا فرم استاندارد حفظ شود.
وقتی باقیمانده صفر شد، افراز کامل را خروجی میدهیم.
ناوردا: مجموع اجزای فعلی بهاضافهٔ r برابر m است؛ آغاز: r=m, B=m, N=0.
معنای فراخوانی Rec(r, B, N): همهٔ راههای کاملکردن پیشوند فعلی a[1..N] را تولید کن.
هر جزء مثبت بعدی را که هم با کران و هم با باقیمانده سازگار است، امتحان میکنیم:
مقدار a[N+1] = i را میگذاریم؛ باقیمانده کم میشود، کران بعدی i میشود و تعداد اجزا یک واحد زیاد میشود.
حالت پایه: اگر r = 0 شد، فقط a[1..N] را خروجی میدهیم و برمیگردیم.
آغاز: پیشوند خالی و کل مجموع باقی است. ناوردا: مجموع اجزای فعلی بهاضافهٔ r برابر m است.
procedure Rec(r, B, N):
if r == 0:
output a[1..N]
return
for i = 1 to min(B, r):
a[N + 1] = i
Rec(r - i, i, N + 1)
Rec(m, m, 0)مثال: همهٔ فراخوانیهای Rec(4,4,0). هر گره، پیشوند انتخابشده و باقیمانده را نشان میدهد؛ برگهای سبز، خروجیاند.
نماد V تعداد گرهها یا فراخوانیهاست؛ اینجا V=12 و تعداد برگها P(4)=5 است.
مسیر سبز ۴ انتخاب دارد. در حالت کلی، طول مسیر حداکثر m است، چون هر جزء دستکم ۱ است.
هر گره روی یک مسیرِ ریشه تا برگ قرار دارد. جمع طول همهٔ مسیرها، تعداد گرهها را از بالا کران میزند.
جستوجو O(V) کار دارد؛ نوشتن خروجیها نیز حداکثر mP(m) جزء است. اینها کران بالا هستند، نه تعداد دقیق عملیات.
اجزا مثبتاند؛ مجموعشان عدد ورودی است و فرم استاندارد دارند.
جزء بعدیِ هر افراز معتبر، در بازهٔ انتخاب الگوریتم جا دارد.
هر افراز استاندارد، فقط یک مسیر انتخاب دارد.
پایانپذیری: با هر جزء مثبت، باقیمانده دستکم یک واحد کم میشود.
هر سطر بهاندازهٔ یک جزء نقطه دارد؛ هر دو نمودار هفت نقطه دارند.
هر جزء مثبت است و سطرها از چپ شروع میشوند؛ پس هر سطر یک نقطه در ستون اول دارد.
هر سکه یک جزء است؛ سه سکه، سه سطر میسازند.
سه نقطهٔ ستون اول، سطر اولِ مزدوج را میسازند.
جزء جدید j = تعداد سطرهایی که تا ستون j میرسند.
سطرهای ۱ و ۲ میرسند؛ سطر ۳ نمیرسد.
هر جزء حداکثر ۲ است و دستکم یک جزء برابر ۲ داریم؛ پس افراز [1,1,1,1] پذیرفته نیست.
دو جزء میخواهیم؛ لازم نیست بزرگترین جزء برابر ۲ باشد.
مزدوج، خانوادهٔ قیدِ بیشینه را به خانوادهٔ قیدِ تعداد میبرد؛ پس میتوان مولد را دوباره استفاده کرد.
نماد P(m,n)، تعداد افرازهای m با دقیقاً n جزء است؛ در مثال، n سکه داریم.
هر افراز، تعداد مشخصی جزء دارد؛ این گروهها همپوشانی ندارند و همهٔ افرازها را پوشش میدهند.
بهترتیب برای تعداد اجزای ۱ تا ۶.
نمونه: P(6,2) = 3؛ پاسخها: [5,1]، [4,2] و [3,3].
نمونه: P(6,3) = 3؛ پاسخها: [4,1,1]، [3,2,1] و [2,2,2].
نماد ⌊x⌋ یعنی بزرگترین عدد صحیحِ کوچکتر یا مساوی x.
فقط برای n ثابت، وقتی m بزرگ میشود:
مزدوجگیری همین تعداد را برای بزرگترین جزء n میدهد؛ در مثال، بزرگترین ارزش سکه n است.
مثال: افرازهای ۶ با دقیقاً ۳ جزء را میشماریم؛ هر افراز فقط در یکی از دو گروه زیر است.
فقط یک جزء ۱ را حذف کن: مجموع یک واحد و تعداد اجزا یک واحد کم میشود.
از هر سه جزء، یک واحد کم کن: مجموع ۳ واحد کم میشود؛ تعداد اجزا همان ۳ میماند.
یک افراز تهی داریم: فهرست خالی، بدون جزء و با مجموع صفر. عدد ۱، تعداد آرایشهاست، نه تعداد اجزا.
با حذف ۱ از افراز [1] به فهرست خالی میرسیم؛ این یک پاسخ معتبر است. حالتهای ناممکن، تعداد صفر دارند.
همهٔ افرازهای عدد m
پیششرط: m ≥ 1
GenerateAll(m):
Rec(m,m,0)نمونهٔ m=7, n=3: (r,B,N) = (7,7,0)
بزرگترین جزء (ارزش سکه) دقیقاً n
پیششرط: 1 ≤ n ≤ m
GenerateLargest(m,n):
a[1] = n
Rec(m-n,n,1)نمونهٔ m=7, n=3: (r,B,N) = (4,3,1)؛ نخست a[1] = 3
Rec(r,B,N):
if r == 0:
output a[1..N]
else:
for i = 1..min(B,r):
a[N+1] = i
Rec(r-i,i,N+1)mnrBNaiدقیقاً، نه حداکثر: Rec(m,n,0) کافی نیست؛ ممکن است هیچ جزء n انتخاب نکند.
هدف: افرازهای m با دقیقاً n جزء؛ مثال: m=7, n=3.
procedure RecPartition2(r, B, N):
if r == 0:
b = ConjPartition(a[1..N])
output b
else:
for i = 1 to min(B, r):
a[N+1] = i
RecPartition2(r-i, i, N+1)
a[1] = n
RecPartition2(m-n, n, 1)برای 1 ≤ n ≤ m: آغاز مانند ۳.۳ است؛ در برگ، بهجای a، مزدوج آن را خروجی میدهیم.
نماد P(m)، تعداد همهٔ افرازهاست؛ P(m,n)، تعداد افرازهای با دقیقاً n جزء است.
| الگوریتم و کار آن | چرا این کران؟ | زمان | حافظه |
|---|---|---|---|
| ۳.۱ · همهٔ افرازها | هر مسیر حداکثر m جزء دارد؛ تعداد برگها P(m) است. مجموع طول مسیرها، کار جستوجو و نوشتن خروجیها را کران میزند. | ||
| ۳.۲ · یک مزدوج | ابتدا a₁ خانه مقداردهی و سپس m−a₁ افزایش انجام میشود: در مجموع m عمل. آرایهٔ خروجی a₁ خانه دارد. | ||
| ۳.۳ · بیشینهٔ n | همان جستوجوی ۳.۱، ولی فقط با P(m,n) برگ؛ برابری تعدادها از مزدوجگیری به دست میآید. | ||
| ۳.۴ · دقیقاً n جزء | جستوجوی ۳.۳، بهاضافهٔ یک مزدوجگیری Θ(m) برای هر یک از P(m,n) خروجیها. |
فرض: عملیات حسابی ثابتزمان و خروجیها یکییکی مصرف میشوند. حافظه شامل پشته و خروجی جاری است، نه ذخیرهٔ همهٔ پاسخها. کرانهای O، کران بالا هستند.
هدف: همهٔ افرازهای ۷ با دقیقاً ۳ جزء را تولید کنیم.
جزء ۳ را از قبل انتخاب کن؛ چهار واحد باقیمانده را با کران ۳ افراز کن.
هر افراز میانی با بزرگترین جزء ۳ را مزدوج کن؛ خروجی دقیقاً ۳ جزء دارد.
الگوریتم ۳.۴ همین ترکیب است: در هر برگِ جستوجوی ۳.۳، بهجای a، مزدوج آن را خروجی بده.
سمت چپ: تمام افرازهای بیشینهٔ ۳؛ سمت راست: تمام افرازهای دقیقاً ۳ جزئی. تناظر یکبهیک، کاملبودن و نبود تکرار را حفظ میکند.
Kreher & Stinson, Combinatorial Algorithms: Generation, Enumeration, and Search, 1999.
با کلیدهای جهت، اسلاید را عوض کنید؛ با کنترلهای گام، تولید و تبدیل افرازها را دنبال کنید.