import sysdef calcoffsets(n, debug=False): allposs = [] for a in range(2,n): for b in range(a+1,n): for c in range(b+1,n): dists = [-1] * n iters = 1; prevlist = [0] while -1 in dists: #print "iters = ",str(iters) nextlist = [] for i in prevlist: t0 = (i+1) % n t1 = (i+a) % n t2 = (i+b) % n t3 = (i+c) % n if dists[t0]==-1: dists[t0] = iters nextlist.append(t0) if dists[t1]==-1: dists[t1] = iters nextlist.append(t1) if dists[t2]==-1: dists[t2] = iters nextlist.append(t2) if dists[t3]==-1: dists[t3] = iters nextlist.append(t3) iters += 1 prevlist = nextlist allposs.append(dists) total = sum(dists) - dists[0] if debug: print "total =",total, "\ttotal/self =", float(total)/float(dists[0]), "\tself =",dists[0], "\toffsets =",[1,a,b,c],dists # Now we have all the possible lists besttotal = 999999999 bestlist = [] bestrat = 0 for list in allposs: tot = sum(list) - list[0] if tot < besttotal: bestrat = float(tot)/float(list[0]) besttotal = tot bestlist = list elif tot == besttotal: rat = float(tot)/float(list[0]) if rat < bestrat: bestrat = rat bestlist = list if debug: print "Best one found:" bestoffsets = [] for i in xrange(len(bestlist)): if bestlist[i] == 1: bestoffsets.append(i) if debug: print "total =",besttotal,"\ttotal/self =", float(besttotal)/float(bestlist[0]), "\tself =",bestlist[0], "\n",bestlist,"\nOffsets: ",bestoffsets # Low total of distances implies maximum branching to new targets # High distance-to-self implies long distance to self # Thus, we seek the smallest total / self return bestoffsetsif __name__ == "__main__": calcoffsets(20)