For p in products-to-replace:
    c = int rand(@total - @chosen)
    For i in the sorted set of already-chosen items:
        last if c < i
        c++
    Insert c into sorted set
    new{p} = total[c]

##</code><code>##

my @random = map $_ x (3 + int rand 5), 'A'..'Z';
my $product_re = qr/\b[A-Z]+(?:\s[A-Z]+)*\b/;

while (<DATA>) {
    my %newname = map { $_ => 1 } /($product_re)/g;
    my @chosen = ();
    for my $prod (keys %newname) {
        my $c = int rand @random - @chosen;
        for (@chosen) {
            last if $c < $_;
            $c++;
        }
        my $i = 0;
        $i++ while $i < @chosen and $chosen[$i] < $c;
        splice @chosen, $i, 0, $c;
        $newname{$prod} = $random[$c];
    }
    s/($product_re)/$newname{$1}/g;
    print;
}
__DATA__
The respondent uses the following products XXX, YYYYY, and ZZZZZZ around the house and they are considering using QQQQQQ, too. They are particularly impressed with ZZZZZZ.
Joe Smith used EGGO WAFFLES, FROSTED FLAKES, and RICE KRISPIES around the house and he is considering using POST SHREDDED WHEAT too. He is particularly impressed with RICE KRISPIES.
Bob likes CATS, DOGS, and ZEBRAS, but particularly CATS.