Ekşi Duyuru

selam, bir permütasyondaki inversion sayısını bulurken sayıları ikili gruplar halinde ayırıyoruz. bunu yaparken de iki kuralımız var:

1. sayılardan biri diğerinden küçük olacak
2. küçük olan sayının permütasyondaki yeri büyük olan sayıdan sonra gelecek

biraz karışık gibi ama oldukça basit, bu soruya bakarsak:

permütasyondaki ilk sayı ile başlayalım, ki bu 6. 6'nın yanına gelebilecek olan sayı 6'dan küçük olmalı ve sırada ondan sonra gelmeli. baştan gidelim ve çiftleri oluşturalım:

- 6'dan sonra 9 geliyor. 9'u 6'nın yanına koyamayız çünkü 6'dan büyük.
- sonraki sayı 4. 4'ü 6'nın yanına koyabiliriz çünkü hem 6'dan küçük hem de sıralamada 6'dan sonra geliyor. böylece ilk sayı çiftimizi oluşturduk. (6,4)
- devam edelim, sonraki sayı 1. 1'i de aynı şekilde 6'nın yanına koyabiliriz. (6,1)
- sonraki sayı 5. aynı şekilde 5'i de koyalım (6,5)
- 11 geliyor sonra ama 11'i koyamayız çünkü 11 6'dan büyük
- sonra 2 geliyor, 2'yi koyabiliriz.

6 ile işimiz bittiğine göre, sıradaki sayıya geçelim ki bu 9 oluyor. şimdi aynı adımları 9 için tekrarlayalım:

- 9'dan sonra 4 geliyor, 4 9'dan küçük olduğu için yeni sayı çiftimiz (9,4) oldu. farkındaysanız 6 9'dan küçük olduğu halde bir çift oluşturamıyoruz çünkü sıralama olarak 9'dan önce
- devam edelim, 4'ten sonra 1 geldi, 1 9'dan küçük olduğu için yeni çiftimiz (9,1) oldu.
- bu şekilde devam edersek 9 ile oluşturabileceğimiz sonraki çiftler (9,5) ve (9,2)

aynı adımları 4, 1, 5, 11 ve 2 için tekrarlarsak şu çiftleri elde ederiz:

(4,1), (4,2), (5,2), (11,2)

daha önceden de elde ettiklerimiz ile birleştirsek elimizdeki çiftler şu şekilde olur:,

(6,4), (6,1), (6,5), (6,2), (9,4), (9,1), (9,5), (9,2), (4,1), (4,2), (5,2), (11,2)

bu çiftlerin sayısı da 12'dir. umarım yardımcı olabilmişimdir :)