Задание №8. Комбинаторика, перестановки и слова по порядку
Что от тебя хотят
Дан алфавит из пары-тройки букв и правила вроде «длина 6, буква А ровно один раз, две гласные подряд нельзя». Нужно либо посчитать, сколько слов подходит, либо найти номер слова в списке «как в словаре». Формулы с сочетаниями и размещениями тоже работают, но на экзамене в них легко ошибиться на ровном месте. У компьютера такой проблемы нет.
Идея: пусть компьютер перебирает
Слов обычно от тысяч до нескольких миллионов, для Python это меньше секунды. Поэтому задача сводится к трём шагам: сгенерировать все слова, отфильтровать по условию, посчитать или найти нужное.
| Что нужно | Чем генерировать |
|---|---|
| Буквы могут повторяться («слова», «коды») | product(алфавит, repeat=N) |
| Каждая буква ровно один раз («перестановки», «анаграммы») | permutations(слово) |
| Нужен номер слова в словаре | счётчик n += 1 + отсортированный алфавит |
Разбор на живом примере
Игорь составляет кодовые слова длины 6 из букв М, А, С, Л, О, причём буква С встречается ровно один раз. Слово не должно начинаться с гласной и оканчиваться согласной. Сколько различных кодовых слов может использовать Игорь?
product выдаёт кортежи вида ('М', 'А', 'С', ...), поэтому каждый кортеж склеиваем в строку через "".join. Дальше условия из задачи переписываются почти дословно: s.count("С") == 1, первая буква s[0] not in "АО", последняя s[-1] in "АО". Ответ: 1536.
Как искать номер слова
Все пятибуквенные слова из букв Ф, О, К, У, С записаны в алфавитном порядке и пронумерованы. Под каким номером в списке идёт последнее слово, которое не содержит букв Ф и содержит ровно две буквы У?
Самое важное правило: алфавит надо отсортировать до генерации. product выдаёт слова в том порядке, в каком лежат буквы, поэтому при отсортированном алфавите список автоматически получается «как в словаре». Нумерация в задачах всегда с единицы, поэтому счётчик n увеличивается до проверки слова: первое слово получает номер 1, а не 0. Это та самая ошибка «на единицу», из-за которой теряют балл при верной идее. «Последнее слово» значит, что номер не печатаем сразу, а запоминаем и выводим после цикла. Ответ: 2313.
permutations честно выдаст 5040 перестановок, из которых уникальных слов всего 1260. Поэтому ответ нужно считать по set.
Разновидности и прототипы задания на экзамене
sorted, слова перебираются через product, а номер ведёт обычный счётчик n.set.Код решения на Python
Запустить код в онлайн-песочницеfrom itertools import product
k = 0
for p in product("МАСЛО", repeat=6):
s = "".join(p)
if s.count("С") == 1 and s[0] not in "АО" and s[-1] in "АО":
k += 1
print(k)from itertools import product
alf = sorted("ФОКУС")
n = 0
for p in product(alf, repeat=5):
n += 1
s = "".join(p)
if "Ф" not in s and s.count("У") == 2:
last = n
print(last)Типичные ошибки
sorted()product('ФОКУС', repeat=5) выдаст слова в порядке букв «Ф, О, К, У, С», а не алфавитном. Номер получится неверным.alf = sorted('ФОКУС'), и уже её отдаём в product.n увеличивать после проверки слова, ответ окажется на единицу меньше.n += 1, потом проверка. В задачах нумерация всегда с первого слова.ГРОБ №8: буква Ё
sorted('ЁЖЕ') выдаст ['Ё', 'Е', 'Ж']: в таблице символов Ё стоит перед А, а не после Е. Если в алфавите задачи есть Ё, нумерация слов съедет.
sorted(alf, key=lambda c: 'АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ'.index(c)). Для задач без Ё (их большинство) достаточно обычного sorted.Лайфхаки на экзамене
- Условие «гласные не стоят рядом»: замени все гласные в слове на одну букву, например «г», и проверь, что
'гг' not in s. Так не придётся перебирать пары руками. - Прежде чем гнать перебор, прикинь размер:
len(алфавит) ** N. Тысяч и даже нескольких миллионов слов Python не заметит, а сотни миллионов уже придётся считать математически. - Сначала прогони код на упрощённом условии, где ответ можно посчитать пальцами (например, слова длины 2), и сравни с головой.