۱ / ۲۵

افرازهای عدد صحیح

تعریف، تولید و افرازهای مقید

امیرحسین محمودی

A person in a teal sweater arranging three gold coins resting on a wooden table.
7=4+2+1
۲ / ۲۵
افرازهای عدد صحیح · تعریف و تولید

افراز عدد صحیح چیست؟

افرازِ یک عدد صحیح مثبت، نوشتن آن به‌صورت مجموع اجزای صحیح مثبت، بدون توجه به ترتیب است.

m=a1+a2+⋯+aN
ai≥1

نمادها

نماد m: مجموعِ موردنظر

نماد N: تعداد اجزا

نماد aᵢ: اندازهٔ جزء شمارهٔ i

اجزا را می‌توان با هر ترتیبی نوشت.

مثال: یک افراز از ۷

a=[4,2,1],N=3
7=4+2+1

هر جزء را مانند ارزش یک سکه در نظر بگیرید.

ترتیب مهم نیست؛ اجزای برابر و افراز تک‌جزئی نیز مجازند.

۳ / ۲۵
افرازهای عدد صحیح · تعریف و تولید

افرازهای ۶: یازده پاسخ متمایز

افراز تک‌جزئیِ ۶ نیز یک پاسخ است؛ سکه‌ها اجزا را نشان می‌دهند.

6=6
6=5+1
6=4+2
6=4+1+1
6=3+3
6=3+2+1
6=3+1+1+1
6=2+2+2
6=2+2+1+1
6=2+1+1+1+1
6=1+1+1+1+1+1
P(6)=11
۴ / ۲۵
افرازهای عدد صحیح · تعریف و تولید

افراز و ترکیب مرتب: آیا ترتیب اجزا مهم است؟

افراز: فقط اندازهٔ اجزا مهم است

4+2≡2+4

یک افراز؛ جابه‌جایی اجزا یا سکه‌ها پاسخ تازه نمی‌سازد.

ترکیب مرتب: ترتیب هم مهم است

(4,2)≠(2,4)

اگر ترتیب اجزا را ثبت کنیم، دو ترکیب مرتب متفاوت داریم.

m=a1+a2+⋯+aN,ai≥1
۵ / ۲۵
افرازهای عدد صحیح · تعریف و تولید

فرم استاندارد: اجزای غیرصعودی

فرم استاندارد یعنی نوشتن اجزای افراز به‌ترتیب غیرصعودی؛ از بزرگ‌ترین به کوچک‌ترین، با امکان تکرار.

تعریف فرم استاندارد

a1≥a2≥⋯≥aN≥1

هر جزء، بزرگ‌تر یا مساوی جزء بعدی است.

اجزای برابر مجازند؛ ترتیب، اکیداً نزولی نیست.

همان افراز، پیش و پس از مرتب‌سازی

مرتب‌سازی غیرصعودی

7=3+2+1+1

فقط ترتیب نوشتن عوض شده است، نه خود افراز. مولد هنگام ساخت پاسخ‌ها همین فرم را حفظ می‌کند.

۶ / ۲۵
افرازهای عدد صحیح · تعریف و تولید

شمارش افرازها با تولید آن‌ها فرق دارد

تابع P(m)، تعداد افرازهای عدد m است.

P(m)∼eπ2m34m3

رشد از هر چندجمله‌ای ثابت سریع‌تر است؛ اما نسبت به مجموع، زیرنمایی است.

نماد ∼ یعنی نسبت دو طرف با بزرگ‌شدن m به ۱ میل می‌کند؛ این برابری دقیق نیست.

P(1),P(2),P(3),P(4),P(5),P(6)=1,2,3,5,7,11

برای P(m) فرمول بستهٔ ساده‌ای با توابع ابتدایی شناخته نشده است؛ اما رشد مجانبی آن معلوم است و در بالا آمده است. محاسبهٔ دقیق تعداد همچنان ممکن است.

۷ / ۲۵
افرازهای عدد صحیح · تعریف و تولید

۳.۱ · تولید همهٔ افرازها: هدف و ایده

هدف: برای عدد صحیح مثبت m، همهٔ افرازهای آن را در فرم استاندارد و هرکدام دقیقاً یک بار تولید کنیم.

چگونه آن‌ها را تولید می‌کنیم؟

۱. هر مقدار مجاز برای جزء بعدی را امتحان می‌کنیم.

۲. مجموع باقی‌مانده را به‌صورت بازگشتی افراز می‌کنیم.

۳. جزءهای بعدی را از جزء فعلی بزرگ‌تر نمی‌گیریم تا فرم استاندارد حفظ شود.

وقتی باقی‌مانده صفر شد، افراز کامل را خروجی می‌دهیم.

حالت لازم برای اجرای این ایده

Rec(r,B,N)

ناوردا: مجموع اجزای فعلی به‌اضافهٔ r برابر m است؛ آغاز: r=m, B=m, N=0.

۸ / ۲۵
افرازهای عدد صحیح · تعریف و تولید

۳.۱ · تولید بازگشتی همهٔ افرازها

معنای فراخوانی Rec(r, B, N): همهٔ راه‌های کامل‌کردن پیشوند فعلی a[1..N] را تولید کن.

هر جزء مثبت بعدی را که هم با کران و هم با باقی‌مانده سازگار است، امتحان می‌کنیم:

1≤i≤min(B,r)

مقدار a[N+1] = i را می‌گذاریم؛ باقی‌مانده کم می‌شود، کران بعدی i می‌شود و تعداد اجزا یک واحد زیاد می‌شود.

Rec(r−i,i,N+1)

حالت پایه: اگر r = 0 شد، فقط a[1..N] را خروجی می‌دهیم و برمی‌گردیم.

Rec(m,m,0)

آغاز: پیشوند خالی و کل مجموع باقی است. ناوردا: مجموع اجزای فعلی به‌اضافهٔ 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)
۹ / ۲۵
افرازهای عدد صحیح · تعریف و تولید

ردگیری تولید افرازهای ۴: پنج خروجی

هدف: تولید همهٔ افرازهای ۴؛ سکه‌ها نمایش اجزا هستند.ورودی: m=4؛ جزء i≤min(B,r) را انتخاب و با حالت (r−i,i,N+1) ادامه می‌دهیم.
اجزای انتخاب‌شده

Rec(r, B, N):
if r == 0: output a[1..N]
for i = 1 to min(B, r):
a[N+1] = i
Rec(r-i, i, N+1)
return to parent
افرازهای کامل
۱۰ / ۲۵
افرازهای عدد صحیح · تعریف و تولید

۳.۱ · از درخت بازگشت تا کران زمان

مثال: همهٔ فراخوانی‌های Rec(4,4,0). هر گره، پیشوند انتخاب‌شده و باقی‌مانده را نشان می‌دهد؛ برگ‌های سبز، خروجی‌اند.

[]r = 4[1]r = 3[1,1]r = 2[1,1,1]r = 1[1,1,1,1]r = 0[2]r = 2[2,1]r = 1[2,1,1]r = 0[2,2]r = 0[3]r = 1[3,1]r = 0[4]r = 0

برگ‌ها و طول مسیرها را بشمار

نماد V تعداد گره‌ها یا فراخوانی‌هاست؛ اینجا V=12 و تعداد برگ‌ها P(4)=5 است.

مسیر سبز ۴ انتخاب دارد. در حالت کلی، طول مسیر حداکثر m است، چون هر جزء دست‌کم ۱ است.

هر گره روی یک مسیرِ ریشه تا برگ قرار دارد. جمع طول همهٔ مسیرها، تعداد گره‌ها را از بالا کران می‌زند.

V≤1+mP(m)
T(m)=O(mP(m))

جست‌وجو O(V) کار دارد؛ نوشتن خروجی‌ها نیز حداکثر mP(m) جزء است. این‌ها کران بالا هستند، نه تعداد دقیق عملیات.

۱۱ / ۲۵
افرازهای عدد صحیح · تعریف و تولید

درستی مولد افراز: اعتبار، کامل‌بودن و یکتایی

هر خروجی معتبر است

اجزا مثبت‌اند؛ مجموعشان عدد ورودی است و فرم استاندارد دارند.

همهٔ پاسخ‌ها ساخته می‌شوند

جزء بعدیِ هر افراز معتبر، در بازهٔ انتخاب الگوریتم جا دارد.

هیچ پاسخ تکراری نداریم

هر افراز استاندارد، فقط یک مسیر انتخاب دارد.

پایان‌پذیری: با هر جزء مثبت، باقی‌مانده دست‌کم یک واحد کم می‌شود.

۱۲ / ۲۵
افرازهای عدد صحیح · تعریف و تولید

نمودار فررز–یانگ و افراز مزدوج

افراز اولیه (Partition)

a=[4,2,1]

افراز مزدوج (Conjugate partition)

a∗=[3,2,1,1]
هر جزء = ارزش یک سکه؛ هر افراز = یک فهرست سکه. نام این نمایش: Ferrers–Young diagram.

هر سطر به‌اندازهٔ یک جزء نقطه دارد؛ هر دو نمودار هفت نقطه دارند.

۱۳ / ۲۵
افرازهای عدد صحیح · تعریف و تولید

چرا ستون اول، تعداد اجزا را می‌شمارد؟

هر جزء مثبت است و سطرها از چپ شروع می‌شوند؛ پس هر سطر یک نقطه در ستون اول دارد.

ورودی: ۳ جزء، یعنی ۳ سطر

a=[4,2,1]
۱۲۳۴۱۴۲۲۳۱

هر سکه یک جزء است؛ سه سکه، سه سطر می‌سازند.

مزدوج: بزرگ‌ترین جزء برابر ۳

b=[3,2,1,1]
۱۲۳۱۳۲۲۳۱۴۱

سه نقطهٔ ستون اول، سطر اولِ مزدوج را می‌سازند.

قضیهٔ ۳.۱: تعداد افرازهای m با دقیقاً n جزء، برابر تعداد افرازهای m با بزرگ‌ترین جزء n است.
دلیل: مزدوج‌گیری یک تناظر یک‌به‌یک و وارون‌پذیر است؛ با دو بار جابه‌جایی سطر و ستون به افراز اول برمی‌گردیم.
۱۴ / ۲۵
افرازهای عدد صحیح · تعریف و تولید

نماد bⱼ یعنی چه؟ یک ستون را بشماریم

bj=|{i:ai≥j}|

جزء جدید j = تعداد سطرهایی که تا ستون j می‌رسند.

راهنمای همهٔ نمادها

ai
اندازهٔ جزء i، یعنی ارزش سکه؛ a₁ بزرگ‌ترین است.
i
شمارهٔ سطر ورودی
N
تعداد کل اجزای ورودی، یعنی سطرها
j
شمارهٔ ستونی که می‌شماریم
bj
جزء مزدوج j: ارتفاع ستون و ارزش سکهٔ تازه
|S|
تعداد اعضای مجموعهٔ S
len(b)
تعداد اجزای افراز مزدوج

مثال: ستون دوم را بشمار

a=[4,2,1],j=2
۱۲۳۴۱۴۲۲۳۱
b2=|{1,2}|=2

سطرهای ۱ و ۲ می‌رسند؛ سطر ۳ نمی‌رسد.

b1=N=3
هر سطر در ستون اول نقطه دارد.
len(b)=a1=4
هر ستون، یک جزء تازه می‌سازد.
۱۵ / ۲۵
افرازهای عدد صحیح · تعریف و تولید

۳.۲ · افراز مزدوج از ارتفاع ستون‌ها

هدف: ساخت یک افراز مزدوج از ارتفاع ستون‌هاورودی: [4,2,1]؛ مزدوج‌گیری قیدِ بیشینه را به قیدِ تعداد اجزا تبدیل می‌کند.
a=[4,2,1]
ConjPartition(a[1..N]):
for j = 1 to a[1]:
b[j] = 1
nPrime = a[1]
for i = 2 to N:
for j = 1 to a[i]:
b[j] = b[j] + 1
return b[1..nPrime]

۱۶ / ۲۵
افرازهای عدد صحیح · تعریف و تولید

افرازهای ۴: بزرگ‌ترین جزء یا تعداد اجزا؟

بزرگ‌ترین جزء دقیقاً ۲

[2,2]
۲ جزء
[2,1,1]
۳ جزء

هر جزء حداکثر ۲ است و دست‌کم یک جزء برابر ۲ داریم؛ پس افراز [1,1,1,1] پذیرفته نیست.

تعداد اجزا دقیقاً ۲

[2,2]
بیشینهٔ ۲
[3,1]
بیشینهٔ ۳

دو جزء می‌خواهیم؛ لازم نیست بزرگ‌ترین جزء برابر ۲ باشد.

[2,1,1]↔[3,1]

مزدوج، خانوادهٔ قیدِ بیشینه را به خانوادهٔ قیدِ تعداد می‌برد؛ پس می‌توان مولد را دوباره استفاده کرد.

۱۷ / ۲۵
افرازهای عدد صحیح · تعریف و تولید

شمارش بر اساس تعداد اجزا

نماد P(m,n)، تعداد افرازهای m با دقیقاً n جزء است؛ در مثال، n سکه داریم.

P(m)=∑n=1mP(m,n)

هر افراز، تعداد مشخصی جزء دارد؛ این گروه‌ها هم‌پوشانی ندارند و همهٔ افرازها را پوشش می‌دهند.

P(6)=1+3+3+2+1+1=11

به‌ترتیب برای تعداد اجزای ۱ تا ۶.

حالت‌های پایه؛ برای m مثبت

P(m,1)=P(m,m)=1
P(m,0)=0,P(0,0)=1
۱۸ / ۲۵
افرازهای عدد صحیح · تعریف و تولید

دو و سه جزء: فرمول‌های دقیق

دقیقاً دو جزء

P(m,2)=⌊m2⌋

نمونه: P(6,2) = 3؛ پاسخ‌ها: [5,1]، [4,2] و [3,3].

دقیقاً سه جزء

P(m,3)=⌊m2+412⌋

نمونه: P(6,3) = 3؛ پاسخ‌ها: [4,1,1]، [3,2,1] و [2,2,2].

نماد ⌊x⌋ یعنی بزرگ‌ترین عدد صحیحِ کوچک‌تر یا مساوی x.

فقط برای n ثابت، وقتی m بزرگ می‌شود:

P(m,n)=Θ(mn−1)

مزدوج‌گیری همین تعداد را برای بزرگ‌ترین جزء n می‌دهد؛ در مثال، بزرگ‌ترین ارزش سکه n است.

۱۹ / ۲۵
افرازهای عدد صحیح · تعریف و تولید

شمارش دقیق: یک مثال، دو گروه

مثال: افرازهای ۶ با دقیقاً ۳ جزء را می‌شماریم؛ هر افراز فقط در یکی از دو گروه زیر است.

P(m,n)=P(m−1,n−1)+P(m−n,n)

گروه اول: دست‌کم یک جزء ۱

فقط یک جزء ۱ را حذف کن: مجموع یک واحد و تعداد اجزا یک واحد کم می‌شود.

[4,1,1]→[4,1]
[3,2,1]→[3,2]
P(5,2)=2

گروه دوم: همهٔ اجزا دست‌کم ۲

از هر سه جزء، یک واحد کم کن: مجموع ۳ واحد کم می‌شود؛ تعداد اجزا همان ۳ می‌ماند.

[2,2,2]→[1,1,1]
P(3,3)=1
P(6,3)=P(5,2)+P(3,3)=2+1=3

یک افراز تهی داریم: فهرست خالی، بدون جزء و با مجموع صفر. عدد ۱، تعداد آرایش‌هاست، نه تعداد اجزا.

P(0,0)=1

با حذف ۱ از افراز [1] به فهرست خالی می‌رسیم؛ این یک پاسخ معتبر است. حالت‌های ناممکن، تعداد صفر دارند.

P(1,1)=P(0,0)+P(0,1)=1+0=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)

راهنمای نمادها

m
مجموع هدف، برابر مبلغ مثال
n
بزرگ‌ترین جزء، یعنی ارزش سکه
r
مجموع باقی‌مانده
B
سقف جزء بعدی
N
تعداد اجزای انتخاب‌شده
a
آرایهٔ اجزا (ارزش سکه‌ها)
i
جزء بعدیِ پیشنهادی

دقیقاً، نه حداکثر: Rec(m,n,0) کافی نیست؛ ممکن است هیچ جزء n انتخاب نکند.

۲۱ / ۲۵
افرازهای عدد صحیح · تعریف و تولید

۳.۳ · افراز با بزرگ‌ترین جزء ۳؛ سکهٔ ۳ واحدی

هدف: افرازهای ۷ با بزرگ‌ترین جزء ۳؛ در مثال، بزرگ‌ترین سکه ۳ است.ورودی: m=7 و n=3. جزء ۳ را از قبل انتخاب می‌کنیم؛ بقیه حداکثر ۳ هستند، پس بزرگ‌ترین جزء دقیقاً ۳ است.
اجزای انتخاب‌شده

m = 7, n = 3
Rec(r, B, N):
if r == 0: output a[1..N]
for i = 1 to min(B, r):
a[N+1] = i
Rec(r-i, i, N+1)
return to parent
افرازهای کامل
۲۲ / ۲۵
افرازهای عدد صحیح · تعریف و تولید

۳.۴ · تولید افراز با دقیقاً ۳ جزء

هدف: افرازهای 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) است. مجموع طول مسیرها، کار جست‌وجو و نوشتن خروجی‌ها را کران می‌زند.
O(mP(m))
O(m)
۳.۲ · یک مزدوجابتدا a₁ خانه مقداردهی و سپس m−a₁ افزایش انجام می‌شود: در مجموع m عمل. آرایهٔ خروجی a₁ خانه دارد.
Θ(m)
Θ(a1)
۳.۳ · بیشینهٔ nهمان جست‌وجوی ۳.۱، ولی فقط با P(m,n) برگ؛ برابری تعدادها از مزدوج‌گیری به دست می‌آید.
O(mP(m,n))
O(m)
۳.۴ · دقیقاً n جزءجست‌وجوی ۳.۳، به‌اضافهٔ یک مزدوج‌گیری Θ(m) برای هر یک از P(m,n) خروجی‌ها.
O(mP(m,n))
O(m)

فرض: عملیات حسابی ثابت‌زمان و خروجی‌ها یکی‌یکی مصرف می‌شوند. حافظه شامل پشته و خروجی جاری است، نه ذخیرهٔ همهٔ پاسخ‌ها. کران‌های O، کران بالا هستند.

۲۵ / ۲۵
افرازهای عدد صحیح · تعریف و تولید

از هدف تا پاسخ: ترکیب الگوریتم‌ها

هدف: همهٔ افرازهای ۷ با دقیقاً ۳ جزء را تولید کنیم.

گام اول · ۳.۳ با بازگشتِ ۳.۱

جزء ۳ را از قبل انتخاب کن؛ چهار واحد باقی‌مانده را با کران ۳ افراز کن.

a1=3,Rec(4,3,1)

گام دوم · ۳.۲ روی هر خروجی

هر افراز میانی با بزرگ‌ترین جزء ۳ را مزدوج کن؛ خروجی دقیقاً ۳ جزء دارد.

b=ConjPartition(a)

الگوریتم ۳.۴ همین ترکیب است: در هر برگِ جست‌وجوی ۳.۳، به‌جای a، مزدوج آن را خروجی بده.

[3,1,1,1,1]→[5,1,1]
[3,2,1,1]→[4,2,1]
[3,2,2]→[3,3,1]
[3,3,1]→[3,2,2]

سمت چپ: تمام افرازهای بیشینهٔ ۳؛ سمت راست: تمام افرازهای دقیقاً ۳ جزئی. تناظر یک‌به‌یک، کامل‌بودن و نبود تکرار را حفظ می‌کند.

Kreher & Stinson, Combinatorial Algorithms: Generation, Enumeration, and Search, 1999.

با کلیدهای جهت، اسلاید را عوض کنید؛ با کنترل‌های گام، تولید و تبدیل افرازها را دنبال کنید.