Комбинаторные задачи о построении слов из букв
В этой статье мы рассмотрим две задачи о построении всех слов из букв, удовлетворяющих определенным условиям.
Мы обратимся к великолепной презентации Константина Полякова «Новые возможности PascalABC.NET и Python для решения задач ЕГЭ по информатике», с которой он выступал для учителей г. Сургута в августе 2022 г. Постановка задач и решения с небольшими изменениями - из этой замечательной презентации.
Задача 1. Сколько можно построить слов из букв В, Е, Н, О, К, в которых встречается сочетание «НК».
Решение. Воспользуемся встроенным методом Cartesian генерации всех комбинаций букв из некоторой последовательности. Затем отфильтруем нужные при помощи метода Where и сосчитаем их количество:
##
'ВЕНОК'.Cartesian(5)
.Where(w -> 'НК' in w)
.Count.Println;Просто и эффективно. Если такая задача встречается на ЕГЭ, то решать её на PascalABC.NET - это праздник :)
Данное решение записано в стиле "цепочка методов" и является очень удобным, поскольку каждый метод в цепочке имеет ясное имя и понятные параметры.
Самое замечательное - это то, что при желании мы можем легко изменить код и посмотреть все эти 485 слов:
##
'ВЕНОК'.Cartesian(5)
.Where(w -> 'НК' in w)
.Println;ВВВНК ВВЕНК ВВННК ВВНКВ ВВНКЕ ВВНКН ВВНКО ВВНКК ВВОНК ВВКНК ВЕВНК ВЕЕНК ВЕННК ВЕНКВ ВЕНКЕ ВЕНКН ВЕНКО ВЕНКК ВЕОНК ВЕКНК ВНВНК ВНЕНК ВНННК ВННКВ ВННКЕ ВННКН ВННКО ВННКК ВНОНК ВНКВВ ВНКВЕ ВНКВН ВНКВО ВНКВК ВНКЕВ ВНКЕЕ ВНКЕН ВНКЕО ВНКЕК ВНКНВ ВНКНЕ ВНКНН ВНКНО ВНКНК ВНКОВ ВНКОЕ ВНКОН ВНКОО ВНКОК ВНККВ ВНККЕ ВНККН ВНККО ВНККК ВОВНК ВОЕНК ВОННК ВОНКВ ВОНКЕ ВОНКН ВОНКО ВОНКК ВООНК ВОКНК ВКВНК ВКЕНК ВКННК ВКНКВ ВКНКЕ ВКНКН ВКНКО ВКНКК ВКОНК ВККНК ЕВВНК ЕВЕНК ЕВННК ЕВНКВ ЕВНКЕ ЕВНКН ЕВНКО ЕВНКК ЕВОНК ЕВКНК ЕЕВНК ЕЕЕНК ЕЕННК ЕЕНКВ ЕЕНКЕ ЕЕНКН ЕЕНКО ЕЕНКК ЕЕОНК ЕЕКНК ЕНВНК ЕНЕНК ЕНННК ЕННКВ ЕННКЕ ЕННКН ЕННКО ЕННКК ЕНОНК ЕНКВВ ЕНКВЕ ЕНКВН ЕНКВО ЕНКВК ЕНКЕВ ЕНКЕЕ ЕНКЕН ЕНКЕО ЕНКЕК ЕНКНВ ЕНКНЕ ЕНКНН ЕНКНО ЕНКНК ЕНКОВ ЕНКОЕ ЕНКОН ЕНКОО ЕНКОК ЕНККВ ЕНККЕ ЕНККН ЕНККО ЕНККК ЕОВНК ЕОЕНК ЕОННК ЕОНКВ ЕОНКЕ ЕОНКН ЕОНКО ЕОНКК ЕООНК ЕОКНК ЕКВНК ЕКЕНК ЕКННК ЕКНКВ ЕКНКЕ ЕКНКН ЕКНКО ЕКНКК ЕКОНК ЕККНК НВВНК НВЕНК НВННК НВНКВ НВНКЕ НВНКН НВНКО НВНКК НВОНК НВКНК НЕВНК НЕЕНК НЕННК НЕНКВ НЕНКЕ НЕНКН НЕНКО НЕНКК НЕОНК НЕКНК ННВНК ННЕНК ННННК НННКВ НННКЕ НННКН НННКО НННКК ННОНК ННКВВ ННКВЕ ННКВН ННКВО ННКВК ННКЕВ ННКЕЕ ННКЕН ННКЕО ННКЕК ННКНВ ННКНЕ ННКНН ННКНО ННКНК ННКОВ ННКОЕ ННКОН ННКОО ННКОК ННККВ ННККЕ ННККН ННККО ННККК НОВНК НОЕНК НОННК НОНКВ НОНКЕ НОНКН НОНКО НОНКК НООНК НОКНК НКВВВ НКВВЕ НКВВН НКВВО НКВВК НКВЕВ НКВЕЕ НКВЕН НКВЕО НКВЕК НКВНВ НКВНЕ НКВНН НКВНО НКВНК НКВОВ НКВОЕ НКВОН НКВОО НКВОК НКВКВ НКВКЕ НКВКН НКВКО НКВКК НКЕВВ НКЕВЕ НКЕВН НКЕВО НКЕВК НКЕЕВ НКЕЕЕ НКЕЕН НКЕЕО НКЕЕК НКЕНВ НКЕНЕ НКЕНН НКЕНО НКЕНК НКЕОВ НКЕОЕ НКЕОН НКЕОО НКЕОК НКЕКВ НКЕКЕ НКЕКН НКЕКО НКЕКК НКНВВ НКНВЕ НКНВН НКНВО НКНВК НКНЕВ НКНЕЕ НКНЕН НКНЕО НКНЕК НКННВ НКННЕ НКННН НКННО НКННК НКНОВ НКНОЕ НКНОН НКНОО НКНОК НКНКВ НКНКЕ НКНКН НКНКО НКНКК НКОВВ НКОВЕ НКОВН НКОВО НКОВК НКОЕВ НКОЕЕ НКОЕН НКОЕО НКОЕК НКОНВ НКОНЕ НКОНН НКОНО НКОНК НКООВ НКООЕ НКООН НКООО НКООК НКОКВ НКОКЕ НКОКН НКОКО НКОКК НККВВ НККВЕ НККВН НККВО НККВК НККЕВ НККЕЕ НККЕН НККЕО НККЕК НККНВ НККНЕ НККНН НККНО НККНК НККОВ НККОЕ НККОН НККОО НККОК НКККВ НКККЕ НКККН НКККО НКККК ОВВНК ОВЕНК ОВННК ОВНКВ ОВНКЕ ОВНКН ОВНКО ОВНКК ОВОНК ОВКНК ОЕВНК ОЕЕНК ОЕННК ОЕНКВ ОЕНКЕ ОЕНКН ОЕНКО ОЕНКК ОЕОНК ОЕКНК ОНВНК ОНЕНК ОНННК ОННКВ ОННКЕ ОННКН ОННКО ОННКК ОНОНК ОНКВВ ОНКВЕ ОНКВН ОНКВО ОНКВК ОНКЕВ ОНКЕЕ ОНКЕН ОНКЕО ОНКЕК ОНКНВ ОНКНЕ ОНКНН ОНКНО ОНКНК ОНКОВ ОНКОЕ ОНКОН ОНКОО ОНКОК ОНККВ ОНККЕ ОНККН ОНККО ОНККК ООВНК ООЕНК ООННК ООНКВ ООНКЕ ООНКН ООНКО ООНКК ОООНК ООКНК ОКВНК ОКЕНК ОКННК ОКНКВ ОКНКЕ ОКНКН ОКНКО ОКНКК ОКОНК ОККНК КВВНК КВЕНК КВННК КВНКВ КВНКЕ КВНКН КВНКО КВНКК КВОНК КВКНК КЕВНК КЕЕНК КЕННК КЕНКВ КЕНКЕ КЕНКН КЕНКО КЕНКК КЕОНК КЕКНК КНВНК КНЕНК КНННК КННКВ КННКЕ КННКН КННКО КННКК КНОНК КНКВВ КНКВЕ КНКВН КНКВО КНКВК КНКЕВ КНКЕЕ КНКЕН КНКЕО КНКЕК КНКНВ КНКНЕ КНКНН КНКНО КНКНК КНКОВ КНКОЕ КНКОН КНКОО КНКОК КНККВ КНККЕ КНККН КНККО КНККК КОВНК КОЕНК КОННК КОНКВ КОНКЕ КОНКН КОНКО КОНКК КООНК КОКНК ККВНК ККЕНК ККННК ККНКВ ККНКЕ ККНКН ККНКО ККНКК ККОНК КККНК
Заметим также, что решение можно еще упростить, используя модификацию метода Count:
##
'ВЕНОК'.Cartesian(5)
.Count(w -> 'НК' in w)
.Println;Подобные решения называются One-liners - это решения, записываемые в одну строку.
Поскольку презентация Константина Полякова решает такие задачи на двух языках - PascalABC.NET и Python - приводим также авторское решение на языке Python:
Эквивалентное решение на Python
from itertools import product
allWords = product('ВЕНОК', repeat=5)
strWords = [ ''.join(x) for x in allWords ]
words = [ w for w in strWords if 'НК' in w ]
print( len(words) ) Наконец, приведем решение в классическом стиле, не использующее встроенные методы. По-существу, мы сами программируем генерацию всех комбинаций букв и подсчет количества слов, удовлетворяющих условию.
Решение без использования методов
##
var word := 'ВЕНОК';
var count := 0;
foreach var c1 in word do
foreach var c2 in word do
foreach var c3 in word do
foreach var c4 in word do
foreach var c5 in word do
begin
var w := c1+c2+c3+c4+c5;
if 'НК' in w then
count += 1;
end;
Print(Count);Теперь рассмотрим более мудрёную задачу из той же презентации (автор задачи А.Н. Носкин).
Задача 2. Все пятибуквенные слова, составленные из букв В, Е, Н, О, К, записаны в алфавитном порядке и пронумерованы, начиная с 1. Под каким номером в списке идёт последнее слово, в котором буквы Н и К встречаются ровно по два раза?
Решение 1. Упорядочим буквы по алфавиту, воспользовавшись методом Order и затем рассмотрим все их комбинации. Результат запишем в промежуточную переменную AllOrdered. Затем используем цикл foreach с индексом (конструкция появилась в PascalABC.NET 3.8.3) и будем переприсваивать индекс переменной ind всякий раз когда встретится слово, удовлетворяющее указанному условию. В итоге в переменной ind будет индекс последнего слова:
##
var AllOrdered := 'ВЕНОК'.Order.Cartesian(5);
var ind := -1;
foreach var w in AllOrdered index i do
if (w.CountOf('Н') = 2) and (w.CountOf('К') = 2) then
ind := i;
Println(ind);2962
Решение 2. Запишем отсортированные комбинации в массив и вызовем метод FindLastIndex с условием:
##
var a := 'ВЕНОК'.Order.Cartesian(5).ToArray;
var ind := a.FindLastIndex(w -> (w.CountOf('Н') = 2)
and (w.CountOf('К') = 2));
Println(ind);Код на Питоне, решающий ту же задачу (автор Е. Джобс) сравним по сложности:
from itertools import product
print( max( n
for n, w in enumerate(
product(sorted('ВЕНОК'), repeat=5),
start=1 )
if w.count('Н') == 2 and
w.count('К') == 2 ) )Мы рассмотрели несколько конструкций и библиотечных методов PascalABC.NET, позволяющих просто и эффективно решать комбинаторные задачи.