If you want a huge speed boost, replace
@rv=($i, @rv, map{$_.':'.$i} @rv);
with
push @rv, $i, map{$_.':'.$i} @rv;

By the way, I found confusing the use of $i for something which is not an index and not even numerical. $part would have worked fine, since it's an element of @parts. Well, it was named @parts before you renamed to worthless @t. Nice algorithm, but shoddy code.