"choosing an item at random is fine"

and also the hardest option. All candidates in a group have to be retained until processing the input data is complete, then all groups have to be checked for multiple candidate items and a random item selected.

If either 'first' or 'last' is also fine then either of those is easier to implement.