Permütasyon

Giriş
Permüstasyonda sıralama önemlidir. Sıralama ve diziliş söz konusu olduğunda permüstasyon kullanılır.

Kombinayonda sıralama önemli değildir. Seçme ve gruplama söz konusu olduğında kombinasyon kullanılır.

Permütasyon Formül

Not : 0! ve 1! sonuç olarak 1 verirler

P (n,r) şeklinde gösterilir. Yani n! / (n-r)! yani n faktöriyel / (n-r) faktöriyel'dir. Bu da aslında n sayısının r sayısı kadar açılması anlamına gelir. Yani P(4,2) dersem 4 sayısı 2 defa açılır. Bu da 4 * 3 anlamına gelir.

Kombinasyon Formül

C (n,r) şeklinde gösterilir. Kısa haliyle C (n,r) = P(n,r) / r! şeklindedir. P(n,r) formülünü açmak gerekir. Yani  n! /r!  (n-r)! faktöriyel'dir. Bu da aslında n sayısının r sayısı kadar açılması / r sayısının sonuna kadar açılmasıdır. Yani C(6,4) dersem 6 sayısı 4 defa açılır, 4 sayısı da sonuna kadar açılır. Bu da 6 * 5 * 4 * 3 / 4 * 3 * 2 *  1 anlamına gelir

Konu Öğrenme Sırası

Bence önce permütasyonu öğrenmek gerekir. Çünkü kombinasyon formül ve mantık olarak Permüstasyona bağlı

Problem Çeşitleri

1. Toplama Kullanarak Çözülenler

Bu problemlerde "veya" kelimesi kullanılır.

Örnek

Ayşe'nin içinde 5 kalem, 3 silgi bulunan iki kutusu vardır. Ayşe 1 kalem veya 1 silgiyi kaç farklı şekilde seçebilir.

Örnek

Bazı problemerde veya kelimesi direkt kullanılmıyor ancak ima ediliyor. 

Ayşe'nin içinde 5 kalem, 3 silgi bulunan iki kutusu vardır. Ayşe bunlardan birisini seçmek isterse kaç farklı şekilde seçebilir.

2. Çarpma Kullanarak Çözülenler

A ve B olayları (burada ve kelimesine dikkat) kaç farklı şekilde seçilebilir şeklinde cümlelerdir.

  2.1 Çok Kümeli Problemler

    2.1 Çok Kümeli Tek Seferlik Problemler - Kümeler Arasında İzlenen Bir Yol Var

Örnek

İstanbul'dan Ankara'ya 2 farklı yol vardır. Ankara'dan Konya'ya 3 farklı yol vardır. İstanbul'dan Konya'ya kaç farklı yoldan gidilebilir

Örnek

Bazen problemleri daha da karmaşık hale getirmek için gidiş dönüş kaç farklı yol vardır şeklinde sorular olabiliyor. Mantık olarak halen aynı. Sadece aynı kümeyi birer kere daha kullanmamız gerekiyor. Aynı soru şöyle de olabilirdi

İstanbul'dan Ankara'ya 2 farklı yol vardır. Ankara'dan Konya'ya 3 farklı yol vardır. İstanbul'dan Konya'ya gidiş dönüş kaç farklı yoldan gidilebilir

Örnek

4 pantalon, 3 ceket, 5 gömleği olan kişi kaç farklı şekilde giyinebilir.

Örnek

Burada sadece dönüş soruluyor. Dolayısıyla kümelerden bir elemanı eksilterek hesaplama yapmak gerekiyor. Ancak olay halen tek seferlik.

İstanbul'dan Ankara'ya 2 farklı yol vardır. Ankara'dan Konya'ya 3 farklı yol vardır. İstanbul'dan Konya'ya giden bir aracın daha öncede kullandığı yolu  kullanmamak üzere kaç farklı yoldan dönebilir

    2.2 Çok Kümeli Tek Seferlik Problemler - Kümeler Arasında İzlenen Bir Yol Var, İlaveten Kestirme Yol Da Var

    Genellikle yol soruları böyle oluyor

Örnek

Normalde İstanbul'dan Ankara'ya, oradan da Konya'ya gitmek gerekir. Ancak İstanbul ve Ankara arasında direkt uçak seferi de olabilir.

İstanbul'dan Ankara'ya 2 farklı yol vardır. Ankara'dan Konya'ya 3 farklı yol vardır. İstanbul'dan Konya'ya da direkt uçuş vardır. İstanbul'dan Konya'ya kaç farklı yoldan gidilebilir

  Burada normal yol permütasyon hesabı yapıldıktan sonra +1 ekleniyor

    2.3 Çok Kümeli Döngü Şeklindeki Problemler

    Bu problemlerde kümeden eleman birer birer eksiltilir

Örnek

Bir iş yeri 5 erkek, 4 kadın adaydan 3'ünü işe almak istiyor. Kadınlardan birini , erkeklerden ikisini işe almak için kaç farklı seçimde bulunabilir

Örnek

3 kişiyi 5 sinema koltuğuna kaç farklı şekilde yerleştirebiliriz.

Örnek

Bazı problemlerde yine döngü olmasına rağmen kaynak eksiltmek gerekmiyor.

6 farklı mektup, 4 farklı posta kutusuna kaç şekilde atılabilir.

  2.2 Tek Kümeli Problemler

  2.2.1 Tek Kümeli Kısıt İçermeyen Problemler

Örnek

3 elemanı olan bir kümeyi kaç farklı şekilde sıralayabiliriz

  2.2.2 Tek Kümeli Kısıt İçeren Problemler

Örnek

3 elemanı olan bir harf kümesinden uzunluğu 2 olan kaç farklı kelime bulabiliriz

C#
Şöyle yaparız.

foreach(var s in "abc".Permute())
  Console.WriteLine(s); // abc 
                        // acb 
                        // bac 
                        // bca 
                        // cba 
                        // cab

Python
Şöyle yaparız.

#!/usr/bin/env python

import sys

def getPermutation(s, prefix=''):
        if len(s) == 0:
                print prefix
        for i in range(len(s)):
                getPermutation(s[0:i]+s[i+1:len(s)],prefix+s[i] )



getPermutation(sys.argv[1],'')

Çıktı olarak şunu alırız.

$ ./foo.py abcd
abcd
abdc
acbd
acdb
adbc
adcb
bacd
badc
bcad
bcda
bdac
bdca
cabd
cadb
cbad
cbda
cdab
cdba
dabc
dacb
dbac
dbca
dcab
dcba

Diğer
Örnek
İki string'in birbirinin permüstasyonu olduğunu anlamak için string'in tüm karakterlerini bir diziye alır ve sıralarız. Eğer sıra aynı ise permütasyondur. Açıklaması şöyle.

Think about the difference between two strings and whether they are the permutations of each other. The solution is simple: They have the same character count and only the character order differs.

Örnek
Şöyle yaparız

public static IEnumerable<T[]> Permute<T>(this IEnumerable<T> source)
{
  return permute(source, Enumerable.Empty<T>());
  IEnumerable<T[]> permutate(IEnumerable<T> remainder, IEnumerable<T> prefix) =>
    !remainder.Any() ? new[] { prefix.ToArray() } :
      remainder.SelectMany((c, i) => permute(
        remainder.Take(i).Concat(remainder.Skip(i+1)).ToArray(),prefix.Append(c)));
}