Arash Taher Fa En

افراز‌

چند روز پیش در کتاب ریاضیات گسسته به مساله افراز‌های یک مجموعه بر خوردم. در کتاب به این موضوع اشاره‌ای نشده بود، اما کاملا مشخص بود که تولید این مجموعه از یک ساختار بازگشتی تبعیت می‌کنه.

از اونجایی‌ که موضوع پیچ و خم داری به نظر می‌رسید ( کافیه به فرمول یافتن تعداد اعضای این مجموعه نگاه بندازید تا بفهمید چی‌ میگم ) تصمیم گرفتم یک برننم برا تولید این مجموعه رو بنویسم.مسائل بازگشتی در حیطه مجموعه‌ها به صورت کلی‌ از قاعده "بودن و نبودن" پیروی می‌کنه. این یکی‌ هم استثنا نبود، هرچند کمی‌ ریزه کاری هم داشت. خلاصه، این راه حلی‌ است که من برای این سوال پیش گرفتم، در زبان پایتون :

# Prints partitions of set : [1,2] -> [[1],[2]], [[1,2]]
def part(lst, current=[], final=[]):
    if len(lst) == 0 :
        if len(current) == 0:
            print (final)
        elif len(current) > 1:
            print ([current] + final)
    else :
        part(lst[1:], current + [lst[0]], final[:])
        part(lst[1:], current[:], final + [[lst[0]]])

Fork me on GitHub