Witam,
Udowodnić, że partition dzieli losową permutację liczb \(\displaystyle{ 1..n}\) na dwa losowe podciągi.
partition jest standardowe. Jako element osiowy wybiera pierwszy element dzielonego ciągu. Następnie idzie od dwóch stron (najpierw od lewej, potem od prawej) i zamienia miejscami gdy trzeba. Na koniec wstawia element osiowy we właściwe miejsce.
Teraz skoro na wejściu jest losowa permutacja, to pierwszy element (oś) też jest losowy. Rozważmy jeden z podciągów (np. lewy). Rozważmy dwa dowolne elementy. Są one względem siebie w jakimś porządku. Jednak równie dobrze mogą być w odwrotnym porządku, wystarczy w oryginalnej permutacji zamienić je miejscami. Ponieważ każda permutacja jest równie prawdopodobna, więc szansa że dwa dowolne elementy są względem siebie w jakimś porządku jest taka sama (tzn dla każdej pary elementów jest równe prawdopodobieństwo ich kolejności względem siebie).
A to już chyba jest uzasadnienie.
Ok ?