PHP How to Make Unique Text from array random result?

My script looks like this:

<?php 
$placeholders = 'City1 - City1 - City1 - City2 - City3 - City4 - City4';
$substitutes  = [
'City1' => ['Orlando','Dallas','Atlanta','Detroit','Houston'],
'City2' => ['Jakarta','Bandung','Surabaya','Medan','Makassar','Surabaya'],
'City3' => ['Atlanta','Tampa','Miami','Houston'],
'City4' => ['Mandalay','Caloocan','Hai Phong','Quezon City'],
];
$replacements = [];
foreach($substitutes as $key => $choices) {
    $random_key = array_rand($choices);
    $replacements[$key] = $choices[$random_key];
}
$spun = str_replace(
    array_keys($replacements),
    array_values($replacements),
    $placeholders
);
echo $spun;
?>

but the result that i get is the same...

Result: Orlando - Orlando - Orlando - Bandung - Miami - Caloocan - Caloocan

I want to make result like this:

Result: Orlando - Houston - Atlanta - Bandung - Miami - Caloocan - Mandalay