Комбінації в Python: як отримати всі варіанти без зайвого коду

Ключові висновки

З цих прикладів можна спостерігати кілька важливих властивостей функції itertools.combinations():

1. Він працює з різними типами ітерованих об’єктів (рядки, списки тощо)

2. Значення rвизначає розмір кожної комбінації

3. Кількість комбінацій визначається за математичною формулою: n! / (r! * (nr)!), де n – довжина ітерованого об’єкта

4. Коли rдорівнює довжині ітерабельного об’єкта, існує лише одна комбінація (весь ітерабельний об’єкт)

5. Коли rперевищує довжину ітерованого об’єкта, повертається порожній список.

Таке розуміння параметрів допоможе вам itertools.combinations()ефективно застосовувати цю функцію у ваших програмах на Python.

Практичне застосування комбінацій

Тепер давайте розглянемо деякі практичні застосування цієї itertools.combinations()функції. Ми розглянемо кілька реальних прикладів, щоб продемонструвати, як цю функцію можна використовувати для вирішення поширених проблем.

Приклад 1: Формування команди

Уявіть, що вам потрібно сформувати команди певного розміру з групи людей. Давайте створимо програму, яка допоможе сформувати всі можливі команди.

1. Створіть новий файл з назвою team_formation.pyв /home/labex/projectкаталозі.

2. Додайте наступний код:

import itertools

def form_teams(members, team_size):
    """Generate all possible teams of the specified size from the list of members."""
    teams = list(itertools.combinations(members, team_size))
    return teams

## List of team members
team_members = ["Alice", "Bob", "Charlie", "David", "Eva", "Frank"]

## Form teams of different sizes
pairs = form_teams(team_members, 2)
trios = form_teams(team_members, 3)

## Display the results
print(f"Total members: {len(team_members)}")
print(f"Members: {team_members}\n")

print(f"Possible pairs (teams of 2): {len(pairs)}")
for i, pair in enumerate(pairs, 1):
    print(f"Team {i}: {' and '.join(pair)}")

print(f"\nPossible trios (teams of 3): {len(trios)}")
for i, trio in enumerate(trios, 1):
    print(f"Team {i}: {', '.join(trio)}")

3. Запустіть скрипт:

python3 team_formation.py

Ви повинні побачити вивід, у якому перелічено всі можливі пари та тріо, які можна сформувати з шести членів команди.

Приклад 2: Пошук усіх підмножин

Ще одним поширеним застосуванням є генерація всіх можливих підмножин заданої множини (також відомої як степенева множина). Реалізуємо це:

1. Створіть новий файл з назвою generate_subsets.pyв /home/labex/projectкаталозі.

2. Додайте наступний код:

import itertools

def generate_all_subsets(items):
    """Generate all possible subsets of the given items."""
    all_subsets = []

    ## Empty set is always a subset
    all_subsets.append(())

    ## Generate subsets of all possible lengths
    for r in range(1, len(items) + 1):
        subsets_of_length_r = list(itertools.combinations(items, r))
        all_subsets.extend(subsets_of_length_r)

    return all_subsets

## Sample set of items
items = ['A', 'B', 'C']

## Generate all subsets
subsets = generate_all_subsets(items)

## Display the results
print(f"Original set: {items}")
print(f"Total number of subsets: {len(subsets)}")
print("All subsets (including the empty set):")

for i, subset in enumerate(subsets):
    if len(subset) == 0:
        print(f"{i+1}. Empty set {{}}")
    else:
        print(f"{i+1}. {set(subset)}")

3. Запустіть скрипт:

python3 generate_subsets.py

Вивід покаже всі можливі підмножини множини {A, B, C}, включаючи порожню множину.

Приклад 3: Генератор комбінацій меню

Давайте створимо практичний додаток, який допоможе ресторану генерувати всі можливі комбінації страв з пунктів меню:

1. Створіть новий файл з назвою menu_combinations.pyв /home/labex/projectкаталозі.

2. Додайте наступний код:

import itertools

def generate_meal_combinations(appetizers, main_courses, desserts):
    """Generate all possible meal combinations with one item from each category."""
    meal_combinations = []

    for app in appetizers:
        for main in main_courses:
            for dessert in desserts:
                meal_combinations.append((app, main, dessert))

    return meal_combinations

def generate_combo_deals(menu_items, combo_size):
    """Generate all possible combo deals of the specified size."""
    return list(itertools.combinations(menu_items, combo_size))

## Menu categories
appetizers = ["Salad", "Soup", "Bruschetta"]
main_courses = ["Pasta", "Steak", "Fish"]
desserts = ["Ice Cream", "Cake", "Fruit"]

## All menu items
all_items = appetizers + main_courses + desserts

## Generate all possible three-course meals
meals = generate_meal_combinations(appetizers, main_courses, desserts)

## Generate all possible 2-item combo deals from the entire menu
combos = generate_combo_deals(all_items, 2)

## Display the results
print("Restaurant Menu Planner\n")

print("Menu Items:")
print(f"Appetizers: {appetizers}")
print(f"Main Courses: {main_courses}")
print(f"Desserts: {desserts}\n")

print(f"Total possible three-course meals: {len(meals)}")
print("Sample meals:")
for i in range(min(5, len(meals))):
    app, main, dessert = meals[i]
    print(f"Meal option {i+1}: {app} + {main} + {dessert}")

print(f"\nTotal possible 2-item combo deals: {len(combos)}")
print("Sample combo deals:")
for i in range(min(5, len(combos))):
    print(f"Combo {i+1}: {' + '.join(combos[i])}")

3. Запустіть скрипт:

python3 menu_combinations.py

import itertools

def find_subsets_with_sum(numbers, target_sum):
    """Find all subsets of numbers that add up to the target sum."""
    results = []

    ## Try combinations of different lengths
    for r in range(1, len(numbers) + 1):
        ## Generate all combinations of length r
        combinations = itertools.combinations(numbers, r)

        ## Check each combination
        for combo in combinations:
            if sum(combo) == target_sum:
                results.append(combo)

    return results

## Example usage
numbers = [3, 5, 2, 7, 4, 9, 1, 8]
target_sum = 10

## Find subsets with sum equal to target_sum
matching_subsets = find_subsets_with_sum(numbers, target_sum)

## Display results
print(f"Numbers: {numbers}")
print(f"Target sum: {target_sum}")
print(f"Number of matching subsets: {len(matching_subsets)}")

if matching_subsets:
    print("Subsets that add up to the target sum:")
    for i, subset in enumerate(matching_subsets, 1):
        print(f"Subset {i}: {subset} (Sum: {sum(subset)})")
else:
    print("No subsets found that add up to the target sum.")

## Let's find subsets for another target sum
second_target = 15
matching_subsets_2 = find_subsets_with_sum(numbers, second_target)

print(f"\nTarget sum: {second_target}")
print(f"Number of matching subsets: {len(matching_subsets_2)}")

if matching_subsets_2:
    print("Subsets that add up to the target sum:")
    for i, subset in enumerate(matching_subsets_2, 1):
        print(f"Subset {i}: {subset} (Sum: {sum(subset)})")
else:
    print("No subsets found that add up to the target sum.")

python3 subset_sum.py

import itertools

def find_subsets_with_sum(numbers, target_sum):
    """Find all subsets of numbers that add up to the target sum."""
    results = []

    ## Try combinations of different lengths
    for r in range(1, len(numbers) + 1):
        ## Generate all combinations of length r
        combinations = itertools.combinations(numbers, r)

        ## Check each combination
        for combo in combinations:
            if sum(combo) == target_sum:
                results.append(combo)

    return results

def main():
    ## Get user input
    try:
        input_str = input("Enter a list of numbers separated by spaces: ")
        numbers = [int(num) for num in input_str.split()]

        target_sum = int(input("Enter the target sum: "))

        ## Find matching subsets
        matching_subsets = find_subsets_with_sum(numbers, target_sum)

        ## Display results
        print(f"\nNumbers: {numbers}")
        print(f"Target sum: {target_sum}")
        print(f"Number of matching subsets: {len(matching_subsets)}")

        if matching_subsets:
            print("Subsets that add up to the target sum:")
            for i, subset in enumerate(matching_subsets, 1):
                print(f"Subset {i}: {subset} (Sum: {sum(subset)})")
        else:
            print("No subsets found that add up to the target sum.")

    except ValueError:
        print("Invalid input. Please enter integers only.")

if __name__ == "__main__":
    main()

python3 interactive_subset_sum.py