Представьте, что вам нужно перебрать все возможные пароли из 4 цифр или найти все способы расставить книги на полке. В реальной жизни такие задачи отнимают много времени, но в Python их можно решить одной строкой кода! Сегодня познакомимся с двумя волшебными инструментами из модуля itertools — permutations и product.
Магия перестановок: itertools.permutations
Перестановки — это все возможные способы упорядочить элементы. Порядок имеет значение! Например, комбинации (1,2) и (2,1) считаются разными.
Как работает permutations?
python
import itertools
# Все перестановки трех элементов
books = ['История', 'Математика', 'Физика']
расстановки = list(itertools.permutations(books))
for i, вариант in enumerate(расстановки, 1):
print(f"{i}. {вариант}")
# Результат:
# 1. ('История', 'Математика', 'Физика')
# 2. ('История', 'Физика', 'Математика')
# 3. ('Математика', 'История', 'Физика')
# 4. ('Математика', 'Физика', 'История')
# 5. ('Физика', 'История', 'Математика')
# 6. ('Физика', 'Математика', 'История')
Перестановки определенной длины
python
# Составляем пары из людей для проекта
сотрудники = ['Анна', 'Борис', 'Виктор']
пары = list(itertools.permutations(сотрудники, 2))
print("Возможные пары:")
for пара in пары:
print(f"{пара[0]} + {пара[1]}")
Декартово произведение: itertools.product
Если permutations работает с одним набором элементов, то product комбинирует элементы из разных наборов. Это как вложенные циклы, но гораздо элегантнее!
Базовое использование
python
import itertools
# Комбинируем цвета и размеры
цвета = ['красный', 'синий']
размеры = ['S', 'M', 'L']
варианты_футболок = list(itertools.product(цвета, размеры))
print("Доступные варианты футболок:")
for цвет, размер in варианты_футболок:
print(f"{цвет} {размер}")
Мощь параметра repeat
python
# Генерируем все двоичные числа длины 3
двоичные_числа = list(itertools.product([0, 1], repeat=3))
print("Все двоичные комбинации длины 3:")
for комбинация in двоичные_числа:
print(''.join(map(str, комбинация)))
Ключевые различия
permutations работает с одной последовательностью и создает упорядоченные комбинации без повторений элементов (если не указана меньшая длина). Порядок элементов важен — (A,B) и (B,A) считаются разными.
product работает с несколькими последовательностями и создает все возможные комбинации, беря по одному элементу из каждой последовательности. Он позволяет элементам повторяться в разных комбинациях.
5 практических задач для закрепления
Задача 1: Генератор анаграмм
python
import itertools
def найти_анаграммы(слово):
"""Найти все анаграммы слова"""
return [''.join(p) for p in itertools.permutations(слово)]
анаграммы = найти_анаграммы("кот")
print(f"Анаграммы слова 'кот': {анаграммы}")
Задача 2: Подбор паролей
python
import itertools
import string
def сгенерировать_пароли(длина):
"""Сгенерировать все пароли заданной длины"""
символы = string.digits # только цифры
return [''.join(p) for p in itertools.product(символы, repeat=длина)]
пароли = сгенерировать_пароли(3)
print(f"Первые 10 паролей из {len(пароли)}: {пароли[:10]}")
Задача 3: Составление расписания
python
import itertools
def составить_расписание(предметы, времена_слотов):
"""Составить все возможные расписания"""
return list(itertools.permutations(предметы, len(времена_слотов)))
предметы = ['Математика', 'Физика', 'Химия']
расписания = составить_расписание(предметы, ['9:00', '10:00', '11:00'])
print("Варианты расписания:")
for i, расписание in enumerate(расписания[:5], 1):
print(f"{i}. {расписание}")
Задача 4: Генератор комбинаций для настольной игры
python
import itertools
def возможные_ходы(кости):
"""Найти все возможные результаты броска костей"""
return list(itertools.product(range(1, кости[0] + 1),
range(1, кости[1] + 1)))
# Для игры с двумя шестигранными костями
ходы = возможные_ходы([6, 6])
print(f"Всего возможных комбинаций: {len(ходы)}")
print(f"Примеры: {ходы[:10]}")
Задача 5: Планирование меню
python
import itertools
def составить_меню(первые_блюда, вторые_блюда, напитки):
"""Составить все возможные комбинации меню"""
return list(itertools.product(первые_блюда, вторые_блюда, напитки))
первые = ['Суп', 'Салат']
вторые = ['Рыба', 'Мясо', 'Паста']
напитки = ['Сок', 'Вода', 'Чай']
меню = составить_меню(первые, вторые, напитки)
print("Варианты комплексных обедов:")
for i, обед in enumerate(меню, 1):
print(f"{i}. {обед[0]} + {обед[1]} + {обед[2]}")
Почему это работает так быстро?
Обе функции возвращают итераторы — специальные объекты, которые генерируют элементы по мере необходимости. Это значит, что даже при работе с миллионами комбинаций память не переполнится, так как в каждый момент времени обрабатывается только один элемент.
python
# Эффективная работа с большими данными
for комбинация in itertools.product(['A', 'B', 'C'], repeat=10):
# Обрабатываем каждую комбинацию по отдельности
обработать(комбинация)
Эти инструменты открывают потрясающие возможности для решения задач из самых разных областей — от криптографии и анализа данных до игровой логики и планирования. Попробуйте применить их в своих проектах!
10 задач на использование itertools.permutations и itertools.product для 10-11 класса
Задача 1: Шифр Цезаря
Условие: Создайте программу для взлома шифра Цезаря методом полного перебора. Шифр Цезаря — это сдвиг каждой буквы на определенное количество позиций в алфавите.
python
import itertools
import string
def взломать_шифр_цезаря(зашифрованный_текст):
алфавит = string.ascii_uppercase
результаты = []
for сдвиг in range(1, 26):
расшифрованный = ''
for буква in зашифрованный_текст:
if буква in алфавит:
новая_позиция = (алфавит.index(буква) - сдвиг) % 26
расшифрованный += алфавит[новая_позиция]
else:
расшифрованный += буква
результаты.append((сдвиг, расшифрованный))
return результаты
# Пример использования
шифр = "IFMMP" # HELLO со сдвигом 1
все_варианты = взломать_шифр_цезаря(шифр)
for сдвиг, текст in все_варианты:
print(f"Сдвиг {сдвиг}: {текст}")
Задача 2: Комбинации сейфа
Условие: Сейф имеет 4-значный код из цифр 0-9. Напишите программу, которая генерирует все возможные комбинации кода и проверяет их на соответствие условию: код должен содержать хотя бы одну четную и одну нечетную цифру.
python
import itertools
def найти_подходящие_коды():
все_коды = itertools.product(range(10), repeat=4)
подходящие = []
for код in все_коды:
четные = sum(1 for цифра in код if цифра % 2 == 0)
нечетные = sum(1 for цифра in код if цифра % 2 == 1)
if четные >= 1 and нечетные >= 1:
подходящие.append(''.join(map(str, код)))
return подходящие
коды = найти_подходящие_коды()
print(f"Найдено {len(коды)} подходящих кодов")
print("Примеры:", коды[:10])
Задача 3: Расстановка ферзей
Условие: На шахматной доске 4×4 нужно расставить 4 ферзя так, чтобы они не били друг друга. Ферзь бьет по горизонтали, вертикали и диагонали.
python
import itertools
def ферзи_не_бьют(расстановка):
for i in range(4):
for j in range(i + 1, 4):
# Проверка на одну горизонталь, вертикаль или диагональ
if расстановка[i][0] == расстановка[j][0] or \
расстановка[i][1] == расстановка[j][1] or \
abs(расстановка[i][0] - расстановка[j][0]) == abs(расстановка[i][1] - расстановка[j][1]):
return False
return True
def найти_расстановки():
все_позиции = [(i, j) for i in range(4) for j in range(4)]
valid_расстановки = []
for расстановка in itertools.permutations(все_позиции, 4):
if ферзи_не_бьют(расстановка):
valid_расстановки.append(расстановка)
return valid_расстановки
решения = найти_расстановки()
print(f"Найдено {len(решения)} решений")
for i, решение in enumerate(решения[:3], 1):
print(f"Решение {i}: {решение}")
Задача 4: Генетический код
Условие: В ДНК используются 4 нуклеотида: A, T, G, C. Создайте программу, которая генерирует все возможные триплеты (последовательности из 3 нуклеотидов) и находит те, которые не содержат повторяющихся элементов.
python
import itertools
def анализировать_триплеты():
нуклеотиды = ['A', 'T', 'G', 'C']
все_триплеты = itertools.product(нуклеотиды, repeat=3)
уникальные = []
с_повторами = []
for триплет in все_триплеты:
if len(set(триплет)) == len(триплет): # Все элементы уникальны
уникальные.append(''.join(триплет))
else:
с_повторами.append(''.join(триплет))
return уникальные, с_повторами
уникальные, с_повторами = анализировать_триплеты()
print(f"Уникальных триплетов: {len(уникальные)}")
print(f"Триплетов с повторами: {len(с_повторами)}")
print("Примеры уникальных:", уникальные[:10])
Задача 5: Команда проекта
Условие: В классе 6 человек: Анна, Борис, Виктор, Галина, Дмитрий, Елена. Нужно сформировать команду из 3 человек для проекта, причем в команде должен быть хотя бы один мальчик и одна девочка.
python
import itertools
def сформировать_команды():
ученики = ['Анна', 'Галина', 'Елена', 'Борис', 'Виктор', 'Дмитрий']
девочки = ['Анна', 'Галина', 'Елена']
мальчики = ['Борис', 'Виктор', 'Дмитрий']
все_команды = list(itertools.combinations(ученики, 3))
valid_команды = []
for команда in все_команды:
девочек_в_команде = sum(1 for ученик in команда if ученик in девочки)
мальчиков_в_команде = sum(1 for ученик in команда if ученик in мальчики)
if девочек_в_команде >= 1 and мальчиков_в_команде >= 1:
valid_команды.append(команда)
return valid_команды
команды = сформировать_команды()
print(f"Возможных команд: {len(команды)}")
for i, команда in enumerate(команды[:10], 1):
print(f"Команда {i}: {', '.join(команда)}")
Задача 6: Анаграммы-палиндромы
Условие: Найдите все анаграммы слова, которые являются палиндромами (читаются одинаково слева направо и справа налево).
python
import itertools
def найти_палиндромы_анаграммы(слово):
все_анаграммы = {''.join(p) for p in itertools.permutations(слово)}
палиндромы = [анаграмма for анаграмма в все_анаграммы
if анаграмма == анаграмма[::-1]]
return палиндромы
# Тестируем на разных словах
слова = ['топот', 'казак', 'радар', 'математика']
for слово in слова:
палиндромы = найти_палиндромы_анаграммы(слово)
print(f"Слово '{слово}': {len(палиндромы)} палиндромов-анаграмм")
if палиндромы:
print(f" Примеры: {палиндромы[:3]}")
Задача 7: Расписание уроков
Условие: Составьте все возможные расписания на день из 5 уроков: Математика, Физика, Химия, История, Литература. Математика и Физика не должны идти подряд.
python
import itertools
def создать_расписания():
предметы = ['Математика', 'Физика', 'Химия', 'История', 'Литература']
все_расписания = list(itertools.permutations(предметы))
valid_расписания = []
for расписание в все_расписания:
valid = True
for i in range(len(расписание) - 1):
if ('Математика' in [расписание[i], расписание[i + 1]] and
'Физика' in [расписание[i], расписание[i + 1]]):
valid = False
break
if valid:
valid_расписания.append(расписание)
return valid_расписания
расписания = создать_расписания()
print(f"Допустимых расписаний: {len(расписания)}")
print("Примеры расписаний:")
for i, расписание in enumerate(расписания[:5], 1):
print(f"{i}. {' -> '.join(расписание)}")
Задача 8: Двоичные последовательности
Условие: Сгенерируйте все двоичные последовательности длины 6, которые содержат ровно три единицы и не имеют двух подряд идущих единиц.
python
import itertools
def специальные_двоичные_последовательности():
все_последовательности = itertools.product([0, 1], repeat=6)
подходящие = []
для последовательность в все_последовательности:
если sum(последовательность) == 3:
# Проверяем, нет ли двух подряд единиц
имеет_подряд_единицы = любой(
последовательность[i] == 1 и последовательность[i + 1] == 1
для i в диапазоне(len(последовательность) - 1)
)
если не имеет_подряд_единицы:
подходящие.append(''.join(map(str, последовательность)))
вернуть подходящие
последовательности = специальные_двоичные_последовательности()
print(f"Найдено {len(последовательности)} специальных последовательностей")
print("Примеры:", последовательности[:10])
Задача 9: Химические соединения
Условие: В химии есть 5 различных атомов: C, H, O, N, S. Создайте все возможные молекулы из 4 атомов, где атом углерода (C) должен быть обязательно.
python
import itertools
def сгенерировать_молекулы():
атомы = ['C', 'H', 'O', 'N', 'S']
все_молекулы = itertools.product(атомы, repeat=4)
молекулы_с_углеродом = []
для молекула в все_молекулы:
если 'C' в молекула:
молекулы_с_углеродом.append(''.join(молекула))
вернуть молекулы_с_углеродом
молекулы = сгенерировать_молекулы()
print(f"Молекул с углеродом: {len(молекулы)}")
print("Примеры молекул:")
для i в диапазоне(0, min(20, len(молекулы)), 5):
print(' '.join(молекулы[i:i+5]))
Задача 10: Комбинации замка
Условие: Кодовый замок имеет 3 диска с цифрами 1-5. Правильный код удовлетворяет условиям:
- Все цифры различны
- Сумма цифр равна 8
- Цифры идут в возрастающем порядке
python
import itertools
def найти_правильные_коды():
все_комбинации = itertools.permutations(диапазон(1, 6), 3)
правильные_коды = []
для код в все_комбинации:
если len(набор(код)) == 3 и sum(код) == 8 и код[0] < код[1] < код[2]:
правильные_коды.append(код)
вернуть правильные_коды
коды = найти_правильные_коды()
print("Правильные коды замка:")
для код в коды:
print(f"Код: {код}, Сумма: {sum(код)}")
Присоединяйтесь к нашему каналу в ДЗЕН «Учитель версии 4.0»!
Будем рады видеть вас среди наших подписчиков. На канале вас ждет эксклюзивный контент:
- Разборы сложных задач по Информатике.
- Советы по использованию Digital-инструментов в учебе.
- Актуальные новости из мира образовательных технологий.
Подписывайтесь, чтобы быть в курсе!
Учитель Информатики
Халтурина Надежда Вячеславовна
Задачи на itertools
1. Генератор уникальных комбинаций для игры
Используй itertools.combinations, чтобы сгенерировать все возможные уникальные пары героев для команды из 5 человек. Дан список имен героев: ['Маг', 'Воин', 'Лучник', 'Жрец', 'Вор', 'Рыцарь']. Выведи все способы выбрать команду из 3 разных героев.
2. Анализ покупок в магазине
Дан список покупок: ['хлеб', 'молоко', 'сыр', 'яблоки', 'бананы']. Используй itertools.permutations, чтобы найти все возможные последовательности, в которых покупатель может выкладывать эти товары на ленту в кассе. Выведи только первые 10 вариантов (иначе их будет слишком много).
3. Система скидок на наборы товаров
У тебя есть три товара: ['A', 'B', 'C']. Магазин предлагает скидки на любые наборы, включая повторяющиеся товары (например, "2A и 1B"). Используй itertools.combinations_with_replacement, чтобы сгенерировать все возможные наборы из 2 товаров (с повторениями). Это поможет аналитику понять, какие комбинации нужно продвигать.
4. Группировка данных по категориям
Дан список кортежей, где первый элемент — категория, а второй — значение: [('A', 10), ('B', 20), ('A', 15), ('C', 5), ('B', 25)]. Используй itertools.groupby, чтобы сгруппировать значения по их категориям и вычислить сумму значений для каждой категории.
Перед группировкой не забудь отсортировать список по категории!
5. Создание ID для новых пользователей
Используй itertools.count, чтобы создать генератор бесконечных уникальных ID для новых пользователей, начиная с 100. Напиши функцию get_new_user_id(), которая при каждом вызове возвращает следующий ID. Протестируй, выведя 5 новых ID.
6. Циклический выбор ведущего
В компании 4 команды: ['Alpha', 'Beta', 'Gamma', 'Delta']. Ежедневно ведущим на летучке становится новая команда по циклу. Используй itertools.cycle, чтобы написать функцию get_next_leader(), которая при каждом вызове возвращает следующую команду-ведущего. Выведи 10 вызовов подряд, чтобы убедиться в цикличности.
7. "Разворачивание" вложенных списков
Дан список списков: [[1, 2, 3], [4, 5], [6, 7, 8, 9]]. Используй itertools.chain, чтобы преобразовать его в один плоский список [1, 2, 3, 4, 5, 6, 7, 8, 9].
8. Генератор всех возможных логинов
Для создания базы тестовых данных нужно сгенерировать все возможные логины, состоящие из 2 букв. Используй itertools.product, чтобы получить все возможные пары из букв 'abc'. Затем усложни задачу: сгенерируй логины длиной от 1 до 3 символов из букв 'ab'.
9. Поиск "соседей" во времени
Дан отсортированный список временных меток (в секундах): [100, 200, 300, 400, 500]. Используй itertools.pairwise (доступно в Python 3.10+), чтобы для каждой пары соседних меток вычислить интервал между ними. Если pairwise нет, создай аналог с помощью zip и срезов.
10. Фильтрация данных по условию (продвинутая)
Используй itertools.compress, чтобы отфильтровать список строк данных на основе списка булевых значений. Дан список городов: ['Москва', 'Лондон', 'Париж', 'Токио', 'Берлин'] и список-маска [True, False, True, False, True]. Выведи только те города, которые соответствуют True в маске.
Советы по решению:
- Импортируй правильно: Начни с import itertools.
- Преобразуй в список: Результаты функций itertools часто являются итераторами. Чтобы увидеть значения, оберни их в list().
- Сортируй для groupby: Помни, что itertools.groupby группирует только подряд идущие элементы. Почти всегда данные нужно сортивать по тому же ключу перед группировкой.
Удачи в практике! Эти задачи охватывают 90% случаев использования itertools в реальных проектах.
#Python #Программирование #Комбинаторика #itertools #Permutations #Product #Алгоритмы #Разработка #DataScience #Python #Программирование #Комбинаторика #itertools #Permutations #Product #Образование #10Класс #Алгоритмы #Задачи