← Bergeç Arşiv
The Art of Computer Programming serisi · 05.10.2026 · 4 dk okuma

Knuth'un Kitabından Bir Soru

Bölüm III — Yığınla Elde Edilen Permütasyonlar
Yazar: Yasin Aydın

Knuth'un Kitabından Bir Soru (I) yazısında 1,2,3,4,\dots,n olarak numaralandırılmış vagonların yığın kullanılarak kaç farklı şekilde çıkış bölgesinde sıralanabileceğini bulmuştuk. Bu yazıda ise bir sıralamanın yığın kullanılarak elde edilebilmesi için gerek ve yeter koşulu vereceğiz.

Problem

Bir demiryolu hattının giriş tarafında, soldan sağa doğru sıralanmış ve 1,2,3,4,\dots,n olarak numaralandırılmış n vagon bulunduğunu düşünelim. Vagonlar yalnızca belirtilen yönlerde hareket edebilir ve birbirlerinin üzerinden atlayamaz. Vagonların çıkışa taşınması stack (yığın) işlemleri kullanılarak gerçekleştirilir:

Giriş ve çıkış hatlarıyla bir yığın (stack) bölgesini gösteren demiryolu şeması
Şekil 1: Kaynak: D. E. Knuth, The Art of Computer Programming, Cilt 1.

Buna göre, çıkış bölgesinde p_1p_2\dots p_n permütasyonunun elde edilmesi için gerek ve yeter koşul i<j<k olup p_j<p_k<p_i sağlayan indislerin bulunmamasıdır, kanıtlayın.

Çözüm

Önce gerekliliği kanıtlayalım. Çelişki elde etmek için p_1p_2\dots p_n permütasyonunun yığın kullanılarak elde edilebildiğini ve i<j<k olup p_j<p_k<p_i sağlayan indislerin bulunduğunu varsayalım.

Vagonlar birbirleri üzerinden atlayamadığı için küçük numaralı vagon büyük numaralı vagondan önce yığına girer. Dolayısıyla, önce p_j, sonra p_k, en son p_i yığına girer. Şimdi p_i'nin çıkış bölgesine taşındığı anı düşünelim. j,k>i olduğundan p_j ve p_k çıkışta p_i'den sonra yer alır. Bu anda p_j ve p_k hâlâ yığındadır ve p_j, yığına daha önce girdiği için p_k'nın altındadır.

Öte yandan j<k olduğundan p_j, p_k'den önce çıkışa taşınmalıdır. Fakat yığından yalnızca en üstteki vagon çıkabilir ve p_k, p_j'nin üstündedir. Bu bir çelişkidir. Dolayısıyla yığın kullanılarak elde edilebilen bir permütasyonda i<j<k olup p_j<p_k<p_i sağlayan indisler bulunamaz.

Gereklilik kanıtının dört adımı: (a) p_j ve p_k yığında, p_i girişte; (b) p_i yığına girer; (c) p_i çıkışa taşınır; (d) p_k, p_j'nin üstünde kalır
Şekil 2: Teoremin gereklilik kanıtındaki adımları gösteren diyagram. Bu diyagram Claude tarafından hazırlanmıştır.

Şimdi yeterliliği kanıtlayalım. Kanıtı karşıt ters yöntemi ile yapacağız. Kanıtlamak istediğimiz önerme, p_1p_2\dots p_n permütasyonunda i<j<k olup p_j<p_k<p_i eşitsizliğini sağlayan indisler bulunmuyorsa, bu permütasyonun çıkış bölgesinde yığın işlemleri ile elde edilebilir olduğudur. Mantık kuralları gereği bu önerme, “bir permütasyon yığın tarafından elde edilemiyorsa, o permütasyonda i<j<k olup p_j<p_k<p_i sağlayan indisler bulunur” önermesine denktir. Kanıtımıza bu denkliği kullanarak devam edeceğiz.

Karşıt tersi kanıtlamak için, verilen bir p_1p_2\dots p_n permütasyonunun yığın işlemleriyle elde edilip edilemeyeceğine karar veren Algoritma 1'i inceleyelim.

Algoritma 1, Yığınla-Elde-Edilebilir(p, n): S boş yığın, g = 1; j = 1'den n'e kadar: g ≤ p_j oldukça S.push(g) ve g = g + 1; S.top() ≠ p_j ise false döndür; S.pop(). Sonunda true döndür.

Bu algoritma her j pozisyonu için önce giriş bölgesinden p_j'ye kadar olan vagonları yığına taşır. Eğer p_j vagonu giriş bölgesinde değilse önceden yığına taşınmıştır ve while döngüsü bir şey yapmaz. Daha sonra yığının en üstündeki vagon p_j ise onu çıkışa götürür. Ancak eğer p_j yığının tepesinde değilse yığında onun üstünde en az bir vagon daha vardır ve algoritma False döndürür. Bu yöntemle her iterasyonda hedef vagonu yığından çıkışa taşıyabiliyorsak bu permütasyon elde edilebilir.

Örneğin n=4 ve 4312 permütasyonu için algoritmayı uygulayalım. İlk iterasyonda hedef vagonumuz 4 olduğu için tüm vagonları yığına taşırız. Yığının tepesindeki vagon 4 olduğu için onu çıkışa taşırız. Şu an hedef vagonumuz 3 ve zaten yığının tepesinde olduğu için onu da çıkışa taşıyabiliriz. Sıradaki hedef 1 ve zaten yığında ancak yığının tepesinde 2 olduğu için bu permütasyon yığınla elde edilemez.

Şimdi teoremin kanıtına geri dönelim ve p_1p_2\dots p_n permütasyonunun yığınla elde edilemediğini varsayalım. Bu durumda Algoritma 1 True döndüremez, çünkü True döndürdüğünde permütasyonu elde etmiş olur. Yani p_1p_2\dots p_n için Algoritma 1 False döndürür. Yeterliliğin karşıt tersini göstermek için p_1p_2\dots p_n permütasyonunda i<j<k olup p_j<p_k<p_i sağlayan indisler bulacağız.

Algoritma 1 False döndürdüğü için öyle bir j adımı vardır ki o adımda p_j yığındadır ve yığının tepesinde p_j'den farklı bir vagon vardır. O vagon x olsun. Vagonlar yığına artan sırayla girdiği için yığın tepeden aşağıya doğru monoton azalandır ve x>p_j'dir. Ayrıca x, j. adımda çıkışta olmadığı için x \notin \{p_1,p_2,\dots,p_{j-1}\} olur. Dolayısıyla permütasyonda x, p_j'den sonra yer alır. Yani eğer x, permütasyonun k. sırasındaysa j<k olur.

Şimdi p_i = \max\{p_1,p_2,\dots,p_{j-1}\} olsun. Algoritma ilk adımda durmadığı için j \ge 2'dir ve görüldüğü üzere i<j'dir. Eğer p_i'nin p_k'den büyük olduğunu kanıtlarsak kanıtımız bitmiş olacak. Çelişki elde etmek için p_i'nin p_k'den küçük olduğunu varsayalım. p_i<p_j durumunu ve p_j<p_i durumunu ayrı ayrı inceleyelim. İlk j-1 adımda yalnızca p_i'ye kadar olan vagonlar yığına taşınır. Eğer p_i<p_j ise (j-1). adımda p_j hâlâ giriş bölgesindedir, j. adımda yığına taşınır ve en üstte olur. Bu, algoritmanın j. adımda durmasıyla çelişir. Eğer p_j<p_i ise j. adımda yığına yeni vagon taşınmaz ve p_k, p_i'den büyük olduğu için yığında bulunmaz. Bu da j. adımda p_k'nin yığının en üstünde olmasıyla çelişir. Dolayısıyla p_i>p_k olur. Böylece i<j<k olup p_j<p_k<p_i sağlayan indisler bulduk ve kanıtı tamamladık.∎

Kaynakça

  1. D. E. Knuth, The Art of Computer Programming, Cilt 1: Fundamental Algorithms, 3. baskı, Addison-Wesley, 1997, Bölüm 2.2.1, Alıştırma 5.

Okumaya devam

Knuth’un Kitabından Bir Soru dizisi · 3 / 3

← Önceki: Knuth’un Kitabından Bir Soru (II)

Konular: Kombinatorik

Bunları da okuyun

  1. Knuth’un Kitabından Bir Soru (I) · 09.11.2025
  2. Enigma Bölüm 1: Matematiksel Ön Hazırlık · 05.02.2026
  3. Enigma Bölüm 3: Enigmanın Çözülmesi · 07.02.2026

Yorumlar

Beğenmek ya da yorum yazmak için GitHub hesabıyla giriş yapmanız gerekir.