Блог Scala Функ. программирование Классы типов Алгоритмы Библиотеки Упражнения Ресурсы

Сочетание

Сочетания из n объектов по k — это возможные варианты выбора k различных элементов из n объектов без учета порядка расположения этих элементов.

Приведем пример сочетаний из пяти объектов {a, b, c, d, e} по три: abc, abd, abe, acd, ace, ade, bcd, bce, bde, cde.

Вычисление

Подсчитать общее число сочетаний из n объектов по k можно так: существует n(n − 1)...(n − k + 1) способов выбора первых k объектов в перестановке, причем каждое сочетание из k элементов встречается ровно k! раз, так как для любого набора из k объектов существует k! перестановок. Поэтому для числа сочетаний из n элементов по k, которое мы обозначим через \(\binom{n}{k}\), получаем следующую формулу:

Формула 1: \(\binom{n}{k} = \frac{n(n - 1)...(n - k + 1)}{k(k - 1)...(1)}\)

Величины \(\binom{n}{k}\) (читается “число сочетаний из n по k”) называются биномиальными коэффициентами.

Алгоритм:

Пример:

Рассмотрим пример вычисления числа сочетаний \(\binom{n}{k}\).

Предположим, что n = 5 и k = 2.

Таким образом, число сочетаний \(\binom{5}{2} = 10\).

Оценка:

Код:

@tailrec
def binomialCoefficient(n: Int, k: Int): BigInt =
  if k < 0 || k > n then BigInt(0)
  else if k > (n / 2) then binomialCoefficient(n, n - k)
  else
    val (num, den) = (0 until k).foldLeft((BigInt(1), BigInt(1))) {
      case ((num, den), i) =>
        (num * BigInt(n - i), den * BigInt(k - i))
    }
    num / den
    
binomialCoefficient(100, 32)
// 143012501349174257560226775

Метрики:

Вычисление числа сочетаний из 100000 по 50000 занимает примерно 1,5 секунды.

binomialCoefficient(100000, 50000)
      
// Число тестовых запусков = 10
// Среднее время = 1,455 секунд

Некоторые свойства

A. Факториальное представление.

Формула 2: \(\binom{n}{k} = \frac{n!}{k!(n − k)!}\), целое \(n \geq\) целого \(k \geq 0\).

Эта формула позволяет представлять комбинации факториалов в виде биномиальных коэффициентов, и наоборот.

B. Свойство симметрии.

Формула 3: \(\binom{n}{k} = \binom{n}{n - k}\), целое \(n \geq\) целого \(k \geq 0\).

Эта формула справедлива для всех целых k. Если k отрицательно или больше, чем n, то биномиальный коэффициент равен нулю (при условии, что n — неотрицательное целое число).

C. Внесение-вынесение.

Формула 4: \(\binom{r}{k} = \frac{r}{k}\binom{r - 1}{k - 1}\), целое \(k != 0\).

Эта формула очень полезна для комбинирования биномиального коэффициента с другими частями выражения.

Следствие формулы выше ещё одно соотношение:

Формула 5: \(\binom{r}{k} = \frac{r}{r - k}\binom{r - 1}{k}\)

D. Формула сложения.

Формула 6: \(\binom{r}{k} = \binom{r - 1}{k} + \binom{r - 1}{k - 1}\), целое k,

Каждое значение равно сумме двух значений из предыдущего ряда, причем одно находится в том же столбце, а другое — в ближайшем столбце слева.

Формула может быть доказана, например, из формул 4 и 5:

\(r\binom{r - 1}{k} + r\binom{r - 1}{k - 1} = (r - k)\binom{r}{k} + k\binom{r}{k} = r\binom{r}{k}\)

Формула сложения часто используется в доказательствах индукцией по r, когда r — целое число.

E. Формулы суммирования.

Формула 7: \(\sum_{k=0}^{n}\binom{r+k}{k} = \binom{r}{0} + \binom{r + 1}{1} + ... + \binom{r + n}{n} = \binom{r + n + 1}{n}\), целое \(n \geq 0\).

Формула 8: \(\sum_{k=0}^{n}\binom{k}{m} = \binom{0}{m} + \binom{1}{m} + ... + \binom{n}{m} = \binom{n + 1}{m + 1}\), целое \(m \geq 0\), целое \(n \geq 0\).

F. Биномиальная теорема.

Формула 9: \((x + y)^{r} = \sum_{k}^{}\binom{r}{k}x^{k}y^{r-k}\), целое \(r \geq 0\).

Частный случай формулы для y = 0:

Формула 10: \(\sum_{k}^{}\binom{r}{k}x^{k} = (1 + x)^{r}\), целое \(r \geq 0\) или \(|x| < 1\).

Обобщение формулы бинома:

Формула 11: \((x + y)^{n} = \sum_{k}^{}\binom{n}{k}x(x - kz)^{k - 1}(y + kz)^{n - k}\), целое \(n \geq 0, x \neq 0\).

G. Обращение верхнего индекса.

Следующее тождество непосредственно следует из определения биномиального коэффициента, если каждый член числителя взять с противоположным знаком и умножить на (−1).

Формула 12: \(\binom{r}{k} = (-1)^{k}\binom{k - r - 1}{k}\), целое k.

Простым следствием соотношения выше является формула суммирования:

Формула 13: \(\sum_{k \leq n}^{}\binom{r}{k}(-1)^{k} = \binom{r}{0} - \binom{r}{1} + ... + (-1)^n\binom{r}{n} = (-1)^n\binom{r - 1}{n}\), целое n.

Для целого r можно получить еще одно важное следствие формулы:

Формула 14: \(\binom{n}{m} = (-1)^{n-m}\binom{-(m + 1)}{n - m}\), целое \(n \geq 0\), целое m.

Таким образом, можно переместить n из верхней позиции в нижнюю.

H. Упрощение произведений.

Произведения биномиальных коэффициентов можно выразить несколькими различными способами, расписывая их через факториалы и снова возвращаясь к записи для биномиальных коэффициентов. Например,

Формула 15: \(\binom{r}{m}\binom{m}{k} = \binom{r}{k}\binom{r - k}{m - k}\), целое m, целое k.

Формула выше очень полезна в случаях, когда индекс (а именно — m) находится и в верхней, и в нижней позициях, а нам нужно, чтобы он был только в одном месте.

I. Суммы произведений.

Следующие формулы показывают, чему равны суммы произведения двух биномиальных коэффициентов при различных положениях индекса суммирования k:

Формула 16 (свертка Вандермонда): \(\sum_{k}^{}\binom{r}{k}\binom{s}{n - k} = \binom{r + s}{n}\), целое n.

Формула 17: \(\sum_{k}^{}\binom{r}{m + k}\binom{s}{n + k} = \binom{r + s}{r - m + n}\), целое m, целое n, целое \(r \geq 0\).

Формула 18: \(\sum_{k}^{}\binom{r}{k}\binom{s + k}{n}(-1)^{r-k} = \binom{s}{n - r}\), целое n, целое \(r \geq 0\).

Формула 19: \(\sum_{k=0}^{r}\binom{r-k}{m}\binom{s}{k - t}(-1)^{k-t} = \binom{r - t - s}{r - t - m}\), целое \(t \geq 0\), целое \(r \geq 0\), целое \(m \geq 0\).

Формула 20: \(\sum_{k=0}^{r}\binom{r-k}{m}\binom{s + k}{n} = \binom{r + s + 1}{m + n + 1}\), целое \(n \geq\) целое \(s \geq 0\), целое \(m \geq 0\), целое \(r \geq 0\).

Формула 21: \(\sum_{k \geq 0}^{}\binom{r - tk}{k}\binom{s - t(n - k)}{n - k}\frac{r}{r - tk} = \binom{r + s - tn}{n}\), целое n.

Генерация сочетаний

Дана коллекция элементов. Сгенерировать все возможные сочетания из этой коллекции заданной длины n. Порядок значения не имеет.

Взято из статьи "Combinatorial Algorithms in Scala"

Алгоритм:

Пример:

Рассмотрим пример вычисления для списка ("a", "b", "c") с длиной комбинаций n = 2.

Оценка:

Код:

extension [A](list: List[A])
  def xcombinations(n: Int): List[List[A]] =
    if n > list.length then Nil
    else if n == list.length then List(list)
    else
      list match
        case _ :: _ if n == 1 => list.map(List(_))
        case hd :: tl =>
          tl.xcombinations(n - 1).map(hd :: _) ::: tl.xcombinations(n)
        case _ => Nil
  
List("a", "b", "c").xcombinations(2)
// List(List("a", "b"), List("a", "c"), List("b", "c"))

Метрики:

Среднее время вычисления сочетаний длины 2 для массива из 1000 элементов составляет несколько миллисекунд.

private val example: List[Int] = (1 to 1000).toList

example.xcombinations(2)
      
// Число тестовых запусков = 10
// Среднее время = 50,046 миллисекунд

Генерация сочетаний всех длин

Дана коллекция элементов. Сгенерировать все возможные сочетания из этой коллекции всех возможных длин. Порядок значения не имеет.

Общее количество комбинаций в наборе длины n можно рассчитать следующим образом:

\(C_{n}^{}= \sum_{1}^{n}C_{n}^{k} = 2^n\)

Взято из статьи "Combinatorial Algorithms in Scala"

Алгоритм:

Оценка:

Код:

extension [A](list: List[A])
  def xsubsets: List[List[A]] =
    (2 to list.length).foldLeft(list.xcombinations(1)): (a, i) =>
      list.xcombinations(i) ::: a
  
List("a", "b", "c").xsubsets
// List(List("a", "b", "c"),
// List("a", "b"), List("a", "c"), List("b", "c"),
// List("a"), List("b"), List("c"))

Метрики:

Среднее время вычисления сочетаний всевозможных длин для массива из 10 элементов составляет несколько миллисекунд.

(1 to 10).toList.xsubsets
      
// Число тестовых запусков = 10
// Среднее время = 2,046 миллисекунд

Ссылки: