solution en bash

Voici une solution à ton problème en bash (4) :

$ cat a
ville1 tata ville2 tbtb
ville2 ville3 tctc tdtd
ville3 tete ville4 tftf
Ville4 tgtg thth ville3
$ ville=( "" Lille Paris Lyon Toulouse )
$ count=$(grep -io "ville[0-9]\+" a | sort -n | awk 'END{gsub("[a-zA-Z]+", ""); print}')
$ for ((i=1; i<count; i++)); do sed -i -r "s@(v|V)ille${i}@${ville[i]}@g" a; done

On ne peut pas mettre d'array dans le string...