Kombinasyon

Formülü
n elemanlı kümenin r elemanı alt kümelerinin sayısını bulmak için formül şöyle
n! / r! (n - r) !
Aslında bu formül uzun. Dahada kolayı için
n * (n-1)... / r! yaparız.  Üst taraf r kadar eksilerek gider.

Örnek
Elimizde şöyle bir kod olsun

String[] operators = {"+", "-", "*"};

Tüm kobinasyonları bulmak için iç içe 3 döngü kurarız. Şöyle yaparız. Döngü kurmadan genel çözümleri için buraya bakınız.

for (int i=0; i < operators.length; ++i) {
  for (int j=0; j < operators.length; ++j) {
    for (int k=0; k < operators.length; ++k) {
      ...
    }
  }
}

Örnek
Elimizde şöyle bir dizi olsun.

[ 1, 2, 3, 4]

2,3 ve 4'lü kombinasyonlar şöyledir

[1] => [1]
[2] => [2]
[3] => [3]
[4] => [4]
[5] => [1, 2]
[6] => [1, 3]
[7] => [1, 4]
[8] => [2, 3]
[9] => [2, 4]
[10] => [3, 4]
[11] => [1, 2, 3]
[12] => [1, 2, 4]
[13] => [1, 3, 4]
[14] => [2, 3, 4]
[15] => [1, 2, 3, 4]

Örnek
C# ile şöyle yaparız.

public static IEnumerable<int[]> Combinations(int n, int k)
{
  var result = new int[k];
  var stack = new Stack<int>();
  stack.Push(0);

  while (stack.Count > 0) {
    int index = stack.Count - 1;
    int value = stack.Pop();

    while (value < n) {
      result[index++] = value++;
      stack.Push(value);

      if (index == k) {
        yield return result;
        break;
      }
    }
  }
}

6,2 yaparsak çıktı olarak şunu alırız
[0,1], [0,2], [0,3], [0,4], [0,5], [1,2], [1,3], [1,4], [1,5], [2,3], [2,4], [2,5], [3,4], [3,5], [4,5]

Kombinasyon Olasılık Problemlerinde Kullanılır
7 koltuklu bir sinemeda John ve Mary'nin yanyana oturmama olasılığı nedir sorusunu çözmek için kombinasyonla önce yanyana olan koltuk sayısını bulmak gerekir.

Ben bu yöntemi sevmiyorum. Daha kolay bir yöntem şöyle
John'un uca oturma ihtimali 2/7. Mary'nin yanına gelmeme ihtimali 5/6.
John'un ortaya oturma ihtimali 5/7. Mary'nin yanına gelmeme ihtimli 4/6.

Şöyle yaparız.

27⋅56+57⋅46=3042=57