title: finding least amount of facilities of a given radius
body: <p>What I'm trying to code is I'm asked to locate the fewest number of facilities, with each facility being located at one of the cities in the data set.<br>
  The data set is set up like this in a list of 4 sublists.  The first list is the city and state, the next list is the coordinates, the next is the population, and last is the mileage.  I'm only worried about the city and state and the mileage between each city.  An example of the data might look like this: 
  (The numbers are made up by the way.)</p>
  
  <pre><code>data = [['Miami FL', 'Fort Meyers FL', 'Oakland CA', 'New York City NY'],
  [[213, 124],[643,234],[754,652],[453,734]],[25345,56782,74563,234755],
  [[0, 200, 2000, 1000],[200, 0, 1900, 950],[2000,1900,0,2500],[1000,950,2500]]
  </code></pre>
  
  <p>The mileage is set up that the index of the city is how far away they are from each other.  </p>
  
  <pre><code>data[3][0] = [0, 200, 2000, 1000] #Miami's distances from other cities
  data[3][0][0] = 0 #how far away miami is from it self
  data[3][0][1] = 200 #how far away Miami is from Fort Meyers
  data[3][2][1] = 1900 how far away Oakland is from Fort Meyers
  </code></pre>
  
  <p>You are given a radius of coverage r (in miles) and asked to locate the fewest number
  of facilities, with each facility being located at one of the 128 cities in the data set,
  so that every one of the 128 cities in the data set is within r miles from some facility.  The returned facilities should be in alphabetical order.  </p>
  
  <p>I have to use a boolean list to check if the city has been served or not. </p>
  
  <p>using this algorithm </p>
  
  <pre><code>Greedy Algorithm for facility location
  1. Initially all cities are unserved.
  2. while there are cities that are unserved:
  3. Pick a city c that "serves" the most unserved cities.
  4. Mark the city c and all cities within r miles of c as served
  </code></pre>
  
  <p>Here is what I have so far:</p>
  
  <pre><code>def locateFacilites(data, r):
      print data
      #creating list served list that has values of all False
      served = [False for x in range(128)]
      #all True list 
      complete = [True for x in range(128)]
  
      finalListOfFacilities = []
      beenServed = 0
      while served != complete:
  
  
          #looping over names of cities
          for index, c in enumerate(data[0]):
  
              if served[index] == False:
                  #if unserved find the list of nearby cities
                  listOfCities = nearbyCities(data[0][index], r, data)
                  unservedList = []
                  #condenses list to all false
                  unservedList = cityUnservedList(listOfCities, data, served, unservedList)
                  print len(unservedList)
                  #Looping through cities to change them to be served
                  if len(unservedList) &gt; beenServed:
                      served = FalseToTrueList(unservedList, data, served)
  
                  if len(unservedList) &gt; beenServed:
  
                      finalListOfFacilities.append(c)
                      beenServed = len(unservedList)
      return finalListOfFacilities
  
  #this function was given.  getDistance returns the distance from one city to another
  def nearbyCities(city, r, data):
      listOfCities = []
      for i in data[0]:
          if getDistance(city, i, data) &lt;=r:
              listOfCities.append(i)
  
      return sorted(listOfCities)
  
  def cityUnservedList(listOfCities, data, served, unservedList):
      for city in listOfCities:
          i = data[0].index(city)
          if served[i] == False:
              unservedList.append(city)
      return unservedList
  
  #converts cities that are false to true if unservedList is greater than beenServed
  def FalseToTrueList(unservedList, data, served):        
      for city in unservedList:
          i = data[0].index(city)
          served[i] = True    
      return served
  </code></pre>
  
  <p>I believe I'm getting close, but I'm getting a runtime error(infinite loop).  Could someone point out if I'm doing something wrong or have a suggestion on where to go?</p>