how to space points on a ring

At work, I had to place some points on a network ring such that each point was maximally distanced from all the other points. However, only some of the locations on the ring were active at any one time. For those that were active, I wanted them to be maximally distanced from all the other nodes. And when I incrementally add the next point, it should always minimize the separation from other nodes and reduce the clustering of nodes, while leaving room for new nodes to be incrementally spaced. This is all very confusing, but I'm writing this blog post so I don't lose this code. When I google'd, I couldn't find any implementation that I could just use, so I want to post my code.

To give a more concrete example, say you have the face of a clock. The first node you chose has no-one to contend with, so you arbitrarily choose node 12 and you're maximally spaced and have minimal clustering. Next, if you were to "pick" another node such that it was maximally distanced from 12, you'd choose 6. The next node code be either 9 o'clock or 3 o'clock ( let's say you always choose in the clockwise direction from the last node that you picked). Thus you choose 9. The next node that will be maximally distanced from the other nodes is 3. Next you'll choose 4:30, because it is half-way between 3 and 6 ( and clockwise from the last picked node). Then you pick 10:30 (not 7:30, because you also want to reduce clustering of nodes). Then 1:30, and then 7:30.

Thus the sequence of points is:

12,6,9,3,4:30,10:30,1:30,7:30

The trick to the algorithm is that if you look at the spacing between the nodes as a fraction of the total clock that you have to travel to get to the next node, you'll get the sequence:

time	iteration	fraction of clock to next node
12	0	Not Applicable
6	1	1/2
9	2	1/4
3	3	1/2
4:30	4	1/8
10:30	5	1/2
1:30	6	1/4
7:30	7	1/2

The relationship between the iteration number and the divisor for the fraction of the clock to the next node is to find the biggest power of 2 that divides evenly into the iteration number and multiply that number by 2.

If you were to extend this algorithm to incrementally evenly space 16 nodes that relationship still holds. I believe that relationship would continue to hold beyond 16 nodes, but that is just my intuition.

Soo.. going on that intuition, the following python code does satisfy my needs to incrementally space nodes on a ring.

size = 64
desired_slots = 16
initial_pos = 0
cur_pos = initial_pos
bin_spaced_slots = [cur_pos]
for slot_num in xrange(1,desired_slots):
    # find the largest power of 2 that evenly divides into 
    # slot_num and then it by 2 to get the phase shift for
    # the placement of the slot
    max_pow2_divisor = 1
    while slot_num % max_pow2_divisor == 0:
        max_pow2_divisor *= 2
    cur_pos = (cur_pos + size/max_pow2_divisor)%size
    bin_spaced_slots.append(cur_pos)
print bin_spaced_slots