پریش‌ها (جایگشت‌های بی‌نقطه‌ی ثابت)

برنامه‌نویسی پویا

تعداد جایگشت‌هایی را که هیچ عضوی سر جای خودش نیست می‌شمارد؛ نسبت آن به همه‌ی جایگشت‌ها به 1/e نزدیک می‌شود.

پریش جایگشتی است که در آن هیچ عضوی سر جای خودش نیست (مسئله‌ی معروف: نامه‌ها در پاکت‌های اشتباه).

ادامه‌ی توضیح ↓

زمان: O(n)
حافظه: O(n)
گریمالدی، فصل ۸

ورودی:

n=8خروجی PDF

۸ نامه به‌تصادف در ۸ پاکت؛ D(8) = ۱۴۸۳۳ حالت هست که هیچ نامه‌ای در پاکت درستش نباشد، حدود ۳۶٫۸٪.

def derangements(n):
# D(k) = (k − 1)·(D(k − 1) + D(k − 2)), with D(0) = 1 and D(1) = 0.
d = [1, 0] + [0] * max(0, n - 1)
fact = 1
rows = [(0, 1, 1, 1.0)]
for k in range(1, n + 1):
fact = fact * k
if k >= 2:
d[k] = (k - 1) * (d[k - 1] + d[k - 2])
rows.append((k, d[k], fact, round(d[k] / fact, 4)))
return d[n]

ناوردا: D[k] تعداد جایگشت‌های k عضو است که هیچ عضوی سر جایش نیست.

شروع اجرا

k—

fact—

جدول هنوز خالی است.

متغیرهای محلی

نارنجی = در همین گام عوض شد

Call stack

derangements()خط 1

گام ۱ از ۴۵

توضیح

ایده

پریش جایگشتی است که در آن هیچ عضوی سر جای خودش نیست (مسئله‌ی معروف: نامه‌ها در پاکت‌های اشتباه).

عضو ۱ را در نظر بگیر؛ به یکی از k − 1 جای دیگر، مثلاً جای j، می‌رود. حالا:

اگر j هم به جای ۱ برود، بقیه k − 2 عضو پریش‌اند: D(k − 2) حالت؛
اگر نرود، مثل این است که j جایی جز «جای ممنوعش» (۱) برود: D(k − 1) حالت.

D(k) = (k − 1) · (D(k − 1) + D(k − 2)),   D(0) = 1,   D(1) = 0

نکته‌ی جالب

با اصل شمول و طرد، D(n) = n! · (1 − 1/1! + 1/2! − … ± 1/n!)؛ پس نسبت D(n)/n! خیلی سریع به 1/e ≈ 0.3679 می‌رسد. ستون آخر جدول همین را نشان می‌دهد.