تولید همه‌ی ترکیب‌ها
همه‌ی زیرمجموعه‌های k عضوی از ۱ تا n را به ترتیب لغت‌نامه‌ای می‌سازد؛ هر عضو بعدی از قبلی بزرگ‌تر است تا هیچ زیرمجموعه‌ای دو بار نیاید.
برای اینکه یک زیرمجموعه دو بار (با ترتیب‌های مختلف) نیاید، عضوها را صعودی می‌چینیم: بعد از x فقط عضوهای بزرگ‌تر از x امتحان می‌شوند.
- زمان:
O(k · C(n, k)) - حافظه:
O(k) - جانسون‌باو، فصل ۶
- گریمالدی، فصل ۱
زیرمجموعه‌های ۳ عضوی از ۵ عضو: C(5, 3) = ۱۰ ترکیب، از 123 تا 345.
def combinations(n, k):current = []rows = []extend(1, n, k, current, rows)return len(rows)def extend(start, n, k, current, rows):if len(current) == k:rows.append(tuple(current))return# Leave room for the items still needed: the last start that can still complete a combination.last = n - (k - len(current)) + 1for x in range(start, last + 1):current.append(x)extend(x + 1, n, k, current, rows)current.pop()
شروع اجرا
جدول هنوز خالی است.
درخت فراخوانی‌های بازگشتی
نارنجی پر = فراخوانی در حال اجرا · حاشیه‌ی نارنجی = هنوز روی پشته · خاکستری = تمام شده
متغیرهای محلی
نارنجی = در همین گام عوض شد
Call stack
- combinations()خط 1
توضیح
ایده
برای اینکه یک زیرمجموعه دو بار (با ترتیب‌های مختلف) نیاید، عضوها را صعودی می‌چینیم: بعد از x فقط عضوهای بزرگ‌تر از x امتحان می‌شوند.
هرس
اگر هنوز r عضو لازم است، شروع از عددی بزرگ‌تر از n − r + 1 بی‌فایده است، چون عضو کافی باقی نمی‌ماند. با این مرز، هر شاخه‌ای که باز می‌شود دست‌کم به یک ترکیب می‌رسد.
هزینه
C(n, k) = n! / (k! (n − k)!) ترکیب، هر کدام k عضو.
در trace به چه چیزی نگاه کنی
- درخت فراخوانی‌ها را با صفحه‌ی «تولید همه‌ی جایگشت‌ها» مقایسه کن: اینجا هر سطح فقط عددهای بزرگ‌تر را امتحان می‌کند.