Would it be possible?

[Keneth]

While I still haven't gotten around to figuring out how the shops are defined (laziness on my part), I don't think it would be impossible to randomize them, it's already done in other parts of the game. Maybe someone who's done some work on the subject could share some more light.