Enuntul zice:

Definiti o procedura PARTITIE-LOMUTO-ALEATOARE care interschimba elementul A[r] cu un element ales aleator din vectorul A[p..r], apoi apeleaza procedura PARTITIE-LOMUTO. Demonstrati ca probabilitatea ca procedura PARTITIE-LOMUTO-ALEATOARE sa returneze valoarea q este aceeasi cu probabilitatea ca procedura PARTITIE-ALEATOARE sa returneze valoarea p+r-q.

PARTITIE aleatoare este procedura lui Hoare, in care se schimba mai intai A[p] cu un element aleator din A[p..r]

Salut! Ma puteti ajuta cu sfaturi la problema 8.2-e din CLR (editia 1, romaneste) ? Mie mi se pare ceva gresit pe acolo. Este la capitolul quicksort

Buna ziua!

In primul rand, sper ca am ales corect categoria in care sa pun acest mesaj.
Daca nu, va rog sa imi spuneti unde sa il postez.

Este vorba de o problema mai veche, Rubik, care s-ar putea sa intereseze
pasionati, dupa cum scria Mihai Scortaru in 2000. Enuntul este:

-----------------
Enunt [prelucrat din GInfo]:

Problema era ca se da o matrice A cu dimensiuni m*n (m si n intre 1 si 100), cu intregi.
O secventa consta in adaugarea unei valori intregi intr-o casuta si a aceleiasi valori in fiecare dintre
cele 2, 3 sau 4 casute adiacente orizontal si vertical, dar nu diagonal. Se cere o succesiune de
secvente care sa duca la o matrice care contine in fiecare casuta o aceeasi valoare, valfin, intre 0 si 1000.
-----------------

Am gasit la vremea aceea o solutie mai rapida asimptotic decat ce se stia (se stia de valfin*n^3).
Am scris un articol cu rezolvarea, din care rasfoind acum nu am priceput nimic, si nu cred ca cineva
a avut rabdarea sa il inteleaga, desi solutia era corecta. M-am gandit din nou si am
gasit o demonstratie si un algoritm foarte frumoase si simple, care poate intereseaza pe cineva.
Solutia e la: http://www.lalescu.ro/liviu/rubik/index.html

Pentru cei care vor sa o ia ca pe o provocare, eu am gasit un O(m*n^2+n^3+valfin*m*n+valfin*n^2).
Trebuie citit CLR (Cormen), 31.4 (descompunere LUP) si inceputul lui 31.5, care contine o remarca
foarte inocenta