[МУЗЫКА] В этом уроке мы рассмотрим еще одну стандартную постановку комбинаторики — сочетание, и начнем с неупорядоченных пар. Давайте рассмотрим следующую постановку на примере довольно стандартной постановки задачи машинного обучения — задачи ранжирования. Пусть у нас есть n документов, и нам нужно отранжировать их по значимости. Один из стандартных подходов требует сравнения каждого текста с каждым из остальных. Сколько сравнений нам придется сделать? Давайте попробуем это решить. К нас есть n документов. Нам нужно сравнить каждый документ с каждым из n − 1 оставшихся. Получается, по правилу произведения, у нас будет n * (n − 1), сравнений будет вот столько. Мы первый документ выбираем n способами, второй n − 1 способом. Все ли здесь правильно? Давайте посмотрим на маленьком примере. Пускай у нас, например, n = 3, и давайте обозначим документы через a, b и c. Наше решение дает 3 * 2 = 6 сравнений. В действительности, если мы просто переберем их руками, их будет три: надо первый документ a сравнить с b, a сравнить с c, и останется только сравнить b и c. Что же пошло не так? Давайте посмотрим внимательно, как устроено наше решение. Мы каждый текст сравниваем с двумя остальными. Давайте просто выпишем все эти сравнения. Мы a сравниваем с b и c, b сравниваем с a и c, c сравниваем с a и b. Вот они выписаны коротко. Заметим, что мы просто посчитали каждое сравнение дважды, и в этом проблема. Теперь мы готовы поправить наше решение. У нас есть n документов. Нам нужно сравнить каждый из них с n − 1 из оставшихся. По правилу произведения у нас будет n * (n − 1) сравнений. Но мы посчитали каждое сравнение два раза: мы посчитали сравнение a и b как сравнение a и b и как сравнение b с a. Как же поправить, чтобы было все хорошо? Давайте просто поделим результат на два. Если мы каждое сравнение посчитали дважды, то правильный ответ получится, если мы просто разделим получившийся результат на два. Получается, что ответ у нас такой: n * (n − 1) / 2, получается, столько сравнений нужно, чтобы отранжировать все документы, чтобы сравнить каждый документ с каждым и отранжировать документы. Получается, что мы посчитали количество неупорядоченных пар из n объектов, их получилось n * (n − 1) / 2. И при этом важно в таких подсчетах следить, что мы каждый объект посчитали ровно один раз. И еще мы можем запомнить на будущее полезную идею, что если мы какой-то объект посчитали несколько раз, например, k раз, и k для всех объектов одинаково, то есть мы все объекты посчитали одно и то же количество раз k, тогда чтобы получить правильный ответ, мы можем просто разделить результат на k. [МУЗЫКА]