Create a list with the greatest gap between known occurrences

This is a python question.

If I have a dictionary of web addresses (key) has an associated name server (value).

A name server can be associated with more than 1 web address, anywhere from 1 to 10 times.

The dictionary is a few hundred addresses long.

a) From this dictionary I want to create a random list of web addresses that must have the greatest gap between the repeated use of the name server used and web address.

b) The random list may be 5-100 times the initial size of the dictionary. Hence (a)

I know how to cycle through, etc but how do I calculate the gap size ? Or better yet, anyone coded something like this before ? Python please. Hope this is clear enough.