ساختمان داده‌ها

مجموعه (set) در پایتون: حذف تکراری‌ها، اجتماع، اشتراک و تفاضل

۱۴ دقیقه مطالعه · به‌روزرسانی ۴ آبان ۱۴۰۵

در درس دیکشنری دیدیم که کلیدها تکراری نمی‌شوند و in روی آن‌ها خیلی سریع است. حالا اگر فقط کلیدها را بخواهیم و مقدارها برایمان مهم نباشد چه؟ این همان مجموعه (set) است: گردایه‌ای از عضوهای یکتا و بی‌ترتیب، دقیقاً مثل مجموعه در ریاضی.

s = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3}
print(s)
print(len(s))

{1, 2, 3, 4, 5, 6, 9}
7

تکراری‌ها خودبه‌خود حذف شدند. ترتیب چاپ هم ممکن است با ترتیب نوشتن فرق داشته باشد: مجموعه ترتیب ندارد، پس اندیس و برش هم ندارد (s[0] خطا می‌دهد).

ساختن مجموعه

a = {1, 2, 3}
b = set([1, 2, 2, 3])        # از لیست
c = set('banana')             # از رشته: حرف‌های یکتا
empty = set()                 # مجموعهٔ خالی

print(a, b, sorted(c))
print(type({}), type(empty))

{1, 2, 3} {1, 2, 3} ['a', 'b', 'n']
<class 'dict'> <class 'set'>

⚠️ دام رایج: {} یک دیکشنری خالی است، نه مجموعهٔ خالی. مجموعهٔ خالی فقط با set() ساخته می‌شود.

عضوهای مجموعه هم مثل کلیدهای دیکشنری باید تغییرناپذیر باشند: عدد، رشته و تاپل مجازند؛ لیست مجاز نیست.

کاربرد اول: حذف تکراری‌ها

emails = ['a@x.ir', 'b@x.ir', 'a@x.ir', 'c@x.ir', 'b@x.ir']

unique = set(emails)
print(len(unique))

# اگر ترتیب اولین ظهور مهم است، از dict کمک بگیرید:
print(list(dict.fromkeys(emails)))

3
['a@x.ir', 'b@x.ir', 'c@x.ir']

list(set(L)) تکراری‌ها را حذف می‌کند ولی ترتیب را تضمین نمی‌کند. اگر ترتیب مهم است، dict.fromkeys یا یک حلقه با مجموعهٔ «دیده‌شده‌ها» به کار ببرید (تمرین ۴).

افزودن و حذف

s = {1, 2}
s.add(3)            # یک عضو
s.add(2)            # تکراری: اتفاقی نمی‌افتد
s.update([4, 5])    # چند عضو
print(s)

s.remove(5)         # اگر نباشد KeyError
s.discard(99)       # اگر نباشد، بی‌صدا رد می‌شود
print(s)

x = s.pop()         # یک عضو دلخواه را برمی‌دارد
print(len(s))

{1, 2, 3, 4, 5}
{1, 2, 3, 4}
3

کاربرد دوم: عضویت سریع

x in L در لیست باید عضوها را یکی‌یکی نگاه کند؛ هرچه لیست بزرگ‌تر، کندتر. اما x in s در مجموعه (مثل کلید دیکشنری) با hash مستقیم سراغ جای عضو می‌رود و تقریباً مستقل از اندازه است:

import time

n = 200_000
L = list(range(n))
S = set(L)

t = time.perf_counter()
for _ in range(200):
    (n - 1) in L
t_list = time.perf_counter() - t

t = time.perf_counter()
for _ in range(200):
    (n - 1) in S
t_set = time.perf_counter() - t

print('list خیلی کندتر است:', t_list > t_set * 10)

list خیلی کندتر است: True

پس هر جا قرار است بارها بپرسید «آیا این را دیده‌ام؟»، مجموعه انتخاب درست است. برای جزئیات بیشتر، جدول پیچیدگی زمانی را ببینید.

عملیات مجموعه‌ای

همان عملیات ریاضی، هم با عملگر و هم با متد:

python_cls = {'sara', 'ali', 'reza', 'mina'}
math_cls   = {'ali', 'mina', 'omid'}

print(sorted(python_cls | math_cls))   # اجتماع: در دست‌کم یکی
print(sorted(python_cls & math_cls))   # اشتراک: در هر دو
print(sorted(python_cls - math_cls))   # تفاضل: فقط پایتون
print(sorted(python_cls ^ math_cls))   # تفاضل متقارن: دقیقاً در یکی

['ali', 'mina', 'omid', 'reza', 'sara']
['ali', 'mina']
['reza', 'sara']
['omid', 'reza', 'sara']

یک فرق کوچک: متدها هر iterable (مثلاً لیست) را هم قبول می‌کنند، ولی عملگرها فقط مجموعه:

a = {1, 2, 3}
print(a.union([3, 4]))
print({1, 2} <= a, {1, 5} <= a)
print(a.isdisjoint({7, 8}))

{1, 2, 3, 4}
True False
True

💡 sorted(...) را در مثال‌ها برای این گذاشتیم که خروجی ترتیب ثابتی داشته باشد. خود مجموعه ترتیب ندارد.

پیمایش و set comprehension

words = ['Apple', 'banana', 'avocado', 'Cherry', 'apple']

firsts = {w[0].lower() for w in words}   # مثل list comprehension، ولی با {}
print(sorted(firsts))

for ch in sorted(firsts):                # پیمایش؛ sorted برای ترتیب ثابت
    print(ch, end=' ')

['a', 'b', 'c']
a b c 

frozenset: مجموعهٔ تغییرناپذیر

مجموعه تغییرپذیر است، پس خودش نمی‌تواند کلید دیکشنری یا عضو مجموعهٔ دیگر باشد. frozenset نسخهٔ یخ‌زده‌ای است که این کار را ممکن می‌کند:

team_scores = {
    frozenset({'sara', 'ali'}): 87,
    frozenset({'reza', 'mina'}): 92,
}
print(team_scores[frozenset({'ali', 'sara'})])   # ترتیب مهم نیست

87

خلاصه

تمرین‌ها (خودآموز، پله‌پله)

مثل درس قبل: اسکلت را پر کنید، اجرا کنید و منتظر OK ✅ باشید. اول راهنمایی، بعد جواب.

سطح ۱: گرم‌کردن

تمرین ۱. پیش‌بینی خروجی. قبل از اجرا روی کاغذ بنویسید:

a = {1, 2, 3, 4}
b = {3, 4, 5}
print(len({1, 1, 2, 2, 2}))
print(sorted(a & b))
print(sorted(a - b))
print(sorted(b - a))
print(len(a | b))
print({3} <= b)
print(type({}))

2
[3, 4]
[1, 2]
[5]
5
True
<class 'dict'>

تمرین ۲. حروف یکتا. تابع unique_letters(s) تعداد حروف متفاوت رشته را برگرداند (فاصله را نشمارید؛ بزرگ و کوچک یکی).

def unique_letters(s):
    # TODO
    pass


# ✅ تست
assert unique_letters('banana') == 3
assert unique_letters('Hello World') == 7
assert unique_letters('') == 0
print('OK ✅')

def unique_letters(s):
    letters = set(s.lower())
    letters.discard(' ')     # اگر فاصله نبود هم خطا نمی‌دهد
    return len(letters)

assert unique_letters('banana') == 3
assert unique_letters('Hello World') == 7
assert unique_letters('') == 0
print('OK ✅')

تمرین ۳. آیا تکراری دارد؟ تابع has_duplicates(L) اگر لیست عضو تکراری داشت True برگرداند. یک خط کافی است!

def has_duplicates(L):
    # TODO
    pass


# ✅ تست
assert has_duplicates([1, 2, 3, 2]) == True
assert has_duplicates([1, 2, 3]) == False
assert has_duplicates([]) == False
print('OK ✅')

def has_duplicates(L):
    return len(set(L)) != len(L)

assert has_duplicates([1, 2, 3, 2]) == True
assert has_duplicates([1, 2, 3]) == False
assert has_duplicates([]) == False
print('OK ✅')

سطح ۲: الگوهای اصلی

تمرین ۴. حذف تکراری با حفظ ترتیب. تابع dedupe(L) لیست تازه‌ای برگرداند که تکراری‌ها از آن حذف شده‌اند ولی ترتیب اولین ظهور حفظ شده است. از dict.fromkeys استفاده نکنید؛ با یک حلقه و یک مجموعهٔ seen بنویسید.

def dedupe(L):
    # TODO
    pass


# ✅ تست
assert dedupe([3, 1, 3, 2, 1, 5]) == [3, 1, 2, 5]
assert dedupe(['b', 'a', 'b']) == ['b', 'a']
assert dedupe([]) == []
print('OK ✅')

def dedupe(L):
    seen = set()
    result = []
    for x in L:
        if x not in seen:
            seen.add(x)
            result.append(x)
    return result

assert dedupe([3, 1, 3, 2, 1, 5]) == [3, 1, 2, 5]
assert dedupe(['b', 'a', 'b']) == ['b', 'a']
assert dedupe([]) == []
print('OK ✅')

تمرین ۵. دوستان مشترک. دیکشنری friends برای هر نفر مجموعهٔ دوستانش را دارد. سه تابع بنویسید:

• common(friends, a, b): دوستان مشترک a و b
• suggest(friends, a): «دوستِ دوستانِ» a که خودِ a نیست و الان دوستش هم نیست
• lonely(friends): کسانی که هیچ دوستی ندارند

friends = {
    'sara': {'ali', 'reza'},
    'ali':  {'sara', 'mina', 'reza'},
    'reza': {'sara', 'ali'},
    'mina': {'ali'},
    'omid': set(),
}

def common(friends, a, b):
    # TODO
    pass

def suggest(friends, a):
    # TODO
    pass

def lonely(friends):
    # TODO
    pass


# ✅ تست
assert common(friends, 'sara', 'ali') == {'reza'}
assert suggest(friends, 'sara') == {'mina'}
assert suggest(friends, 'mina') == {'sara', 'reza'}
assert lonely(friends) == {'omid'}
print('OK ✅')

friends = {
    'sara': {'ali', 'reza'},
    'ali':  {'sara', 'mina', 'reza'},
    'reza': {'sara', 'ali'},
    'mina': {'ali'},
    'omid': set(),
}

def common(friends, a, b):
    return friends[a] & friends[b]

def suggest(friends, a):
    fof = set()
    for f in friends[a]:
        fof |= friends[f]
    return fof - friends[a] - {a}

def lonely(friends):
    return {p for p, fs in friends.items() if not fs}

assert common(friends, 'sara', 'ali') == {'reza'}
assert suggest(friends, 'sara') == {'mina'}
assert suggest(friends, 'mina') == {'sara', 'reza'}
assert lonely(friends) == {'omid'}
print('OK ✅')

تمرین ۶. پنگرام. جمله‌ای که همهٔ ۲۶ حرف انگلیسی را دست‌کم یک بار داشته باشد، پنگرام است. تابع is_pangram(s) و سپس missing_letters(s) را بنویسید. دومی رشته‌ای از حروف جاافتاده را، به ترتیب الفبا، برمی‌گرداند.

import string

def is_pangram(s):
    # TODO
    pass

def missing_letters(s):
    # TODO
    pass


# ✅ تست
assert is_pangram('The quick brown fox jumps over the lazy dog') == True
assert is_pangram('Hello world') == False
assert missing_letters('The quick brown fox jumps over the dog') == 'alyz'
print('OK ✅')

import string

ALPHABET = set(string.ascii_lowercase)

def is_pangram(s):
    return ALPHABET <= set(s.lower())

def missing_letters(s):
    return ''.join(sorted(ALPHABET - set(s.lower())))

assert is_pangram('The quick brown fox jumps over the lazy dog') == True
assert is_pangram('Hello world') == False
assert missing_letters('The quick brown fox jumps over the dog') == 'alyz'
print('OK ✅')

سطح ۳: ترکیبی

تمرین ۷. جفتی با جمع هدف. تابع has_pair_sum(nums, target) بگوید آیا دو عدد در دو جای متفاوت لیست هستند که جمعشان target شود. راه ساده دو حلقهٔ تودرتو است. سعی کنید با یک حلقه و یک مجموعه حلش کنید.

def has_pair_sum(nums, target):
    # TODO
    pass


# ✅ تست
assert has_pair_sum([8, 3, 5, 1], 9) == True     # 8 + 1
assert has_pair_sum([8, 3, 5, 1], 7) == False
assert has_pair_sum([5], 10) == False            # یک ۵ تنها کافی نیست
assert has_pair_sum([5, 5], 10) == True
print('OK ✅')

def has_pair_sum(nums, target):
    seen = set()
    for x in nums:
        if target - x in seen:
            return True
        seen.add(x)
    return False

assert has_pair_sum([8, 3, 5, 1], 9) == True
assert has_pair_sum([8, 3, 5, 1], 7) == False
assert has_pair_sum([5], 10) == False
assert has_pair_sum([5, 5], 10) == True
print('OK ✅')

تمرین ۸. مقایسهٔ دو متن. تابع compare(t1, t2) یک دیکشنری با سه کلید برگرداند: 'both' (کلمه‌های مشترک)، 'only1' و 'only2'، هر کدام به‌صورت لیست مرتب. بعد شباهت دو متن را با شاخص Jaccard حساب کنید: اندازهٔ اشتراک تقسیم بر اندازهٔ اجتماع.

def compare(t1, t2):
    # TODO
    pass

def jaccard(t1, t2):
    # TODO
    pass


# ✅ تست
t1 = 'I like python and I like data'
t2 = 'you like data and you like music'
assert compare(t1, t2) == {
    'both': ['and', 'data', 'like'],
    'only1': ['i', 'python'],
    'only2': ['music', 'you'],
}
assert jaccard(t1, t2) == 3 / 7
assert jaccard('a b', 'a b') == 1
print('OK ✅')

def words(t):
    return set(t.lower().split())

def compare(t1, t2):
    a, b = words(t1), words(t2)
    return {
        'both': sorted(a & b),
        'only1': sorted(a - b),
        'only2': sorted(b - a),
    }

def jaccard(t1, t2):
    a, b = words(t1), words(t2)
    return len(a & b) / len(a | b)

t1 = 'I like python and I like data'
t2 = 'you like data and you like music'
assert compare(t1, t2) == {
    'both': ['and', 'data', 'like'],
    'only1': ['i', 'python'],
    'only2': ['music', 'you'],
}
assert jaccard(t1, t2) == 3 / 7
assert jaccard('a b', 'a b') == 1
print('OK ✅')

🏆 چالش پایانی: سودوکو معتبر است؟

یک جدول ۹×۹ سودوکو (لیستی از ۹ لیست) داریم. خانه‌های خالی با 0 مشخص شده‌اند. تابع valid(board) بررسی کند که در هیچ سطر، ستون و مربع ۳×۳ای، عدد غیرصفرِ تکراری نباشد.

def valid(board):
    # TODO
    pass


# ✅ تست
good = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9],
]
bad_box = [row[:] for row in good]
bad_box[1][1] = 8          # در مربع بالا-چپ دو ۸ (سطر و ستونش سالم است)
bad_col = [row[:] for row in good]
bad_col[8][0] = 5          # ستون اول دو ۵
assert valid(good) == True
assert valid(bad_box) == False
assert valid(bad_col) == False
print('OK ✅')

def ok(cells):
    nums = [x for x in cells if x != 0]
    return len(nums) == len(set(nums))

def valid(board):
    for i in range(9):
        row = board[i]
        col = [board[r][i] for r in range(9)]
        if not ok(row) or not ok(col):
            return False
    for br in (0, 3, 6):
        for bc in (0, 3, 6):
            box = [board[r][c] for r in range(br, br + 3) for c in range(bc, bc + 3)]
            if not ok(box):
                return False
    return True

good = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9],
]
bad_box = [row[:] for row in good]
bad_box[1][1] = 8
bad_col = [row[:] for row in good]
bad_col[8][0] = 5
assert valid(good) == True
assert valid(bad_box) == False
assert valid(bad_col) == False
print('OK ✅')

برای مطالعهٔ بیشتر و تمرین بیشتر

• کتاب Think Python، فصل ۱۸: امکانات بیشتر پایتون: بخش «مجموعه‌ها» در همان ابتدای فصل، از جمله نسخهٔ کوتاه has_duplicates با مجموعه، همان تمرین ۳ همین درس.
• آموزش رسمی پایتون، بخش ساختارهای داده: مجموعه‌ها کنار لیست، تاپل و دیکشنری.
• تمرین تعاملی مجموعه: شش گام با بررسی خودکار.

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