Skip to content

Instantly share code, notes, and snippets.

@maurostorch

maurostorch/cities.py

Last active September 1, 2016 14:23
Show Gist options
  • Save maurostorch/20b9b679073a4c5c28360306f3437c74 to your computer and use it in GitHub Desktop.
Save maurostorch/20b9b679073a4c5c28360306f3437c74 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
cities.py
import sys
a=[18897109,12828837, 9461105, 6371773, 5965343, 5946800, 5582170, 5564635, 5268860, 4552402, 4335391, 4296250, 4224851, 4192887, 3439809, 3279833, 3095313, 2812896, 2783243, 2710489, 2543482, 2356285, 2226009, 2149127, 2142508, 2134411]
CUT=100000000
#a=[1,2,3,4]
#CUT=5
# the recursion
def r(pos, level):
global a
if level == 1:
yield [a[pos]]
else:
for i in range(pos+1,len(a)):
for e in r(i, level-1):
yield [a[pos]]+e
# trying a short path, based on the decreasing average of cities' size
av=len(a)*CUT/sum(a)
#print av # num of elements based on the sum average
s=0
for i in range(1,len(a)):
s=s+a[i-1]-a[i]
difaverage=s/(len(a)-1) # the difference average between pairs
m=av-int(av*av*(difaverage/float(sum(a))))
mm=av+int(av*av*(difaverage/float(sum(a))))
#print m,mm # num of elements (minus,plus) the percentual difaverage
for i in range(len(a)):
for j in range(m,mm):
for k in r(i, j):
s=sum(k)
if s == CUT:
print k, sum(k), j
sys.exit() #stop doing after found
#else:
# sys.stdout.write("\r"+str(s)) # just to follow the process
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment