# Re: Il problema di Matteo all'RSC

**URL:** <https://www.ruby-forum.com/t/re-il-problema-di-matteo-allrsc/149504>\
**Category:** IT\
**Created:** [September 25, 2008, 3:02pm UTC](https://www.ruby-forum.com/t/re-il-problema-di-matteo-allrsc/149504 "2008-09-25T15:02:57Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![gabriele\_renzi](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/g/e19b73/32.png) [@gabriele\_renzi](https://www.ruby-forum.com/u/gabriele_renzi)\
**Post date:** [September 25, 2008, 3:02pm UTC](https://www.ruby-forum.com/t/re-il-problema-di-matteo-allrsc/149504/1 "2008-09-25T15:02:57Z")

</div>

> From: Claudio Petasecca D. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
> To: removed\_email\_address@domain.invalid  
> Sent: Thursday, 25 September, 2008 14:53:23  
> Subject: Re: [ruby-it] Il problema di Matteo all’RSC
> 
> Con Ruby 1.9 (credo) possiamo sfruttare il metodo group\_by, che e’  
> definito anche in Rails:

giovanni non vi ha dato la constraint più interessante: spazio costante.  
L’array va modificato in place effettundo degli swap (con qualche var  
ausiliaria), e in tempo lineare.

Io so la sua soluzione ma mi piacerebbe sapere se qualcuno ha idea del  
limite di complessità raggiungibile.  
per il caso con due partizioni è O(N) credo, dove N è la dimensione della  
partizioni più grande, ma mi chiedo quale sia il caso generale.