title: How to re-order units based on their degree of desirable neighborhood ? (in Processing)
body: <p>I would need help to implement an algorithm allowing the generation of building plans,  that I've recently stumbled on while reading Professor Kostas Terzidis' latest publication: <a href="https://books.google.com/books/about/Permutation_Design.html?id=govtnQEACAAJ&amp;source=kp_book_description&amp;redir_esc=y" rel="noreferrer"><em>Permutation Design: Buildings, Texts and Contexts</em></a> (2014).</p>
  
  <p><strong>CONTEXT</strong></p>
  
  <ul>
  <li>Consider a site (b) that is divided into a grid system (a).</li>
  <li>Let's also consider a list of spaces to be placed within the limits of the site ( c ) and an adjacency matrix to determine the placement conditions and neighboring relations of these spaces (d)</li>
  </ul>
  
  <p><a href="https://i.stack.imgur.com/mCkiS.jpg" rel="noreferrer"><img src="https://i.stack.imgur.com/mCkiS.jpg" alt="enter image description here"></a></p>
  
  <p>Quoting Prof. Terzidis:</p>
  
  <blockquote>
    <p>"A way of solving this problem is to stochastically place spaces within the grid until all spaces are fit and the constraints are satisfied"</p>
  </blockquote>
  
  <p>The figure above shows such a problem and a sample solution (f).</p>
  
  <p><strong>ALGORITHM (as briefly described in the book)</strong></p>
  
  <p>1/ "Each space is associated with a list that contains all other spaces sorted according to their degree of desirable neighborhood."</p>
  
  <p>2/ "Then each unit of each space is selected from the list and then one-by-one placed randomly in the site until they fit in the site and the neighboring conditions are met. (If it fails then the process is repeated)"</p>
  
  <p>Example of nine randomly generated plans:</p>
  
  <p><a href="https://i.stack.imgur.com/35i4I.jpg" rel="noreferrer"><img src="https://i.stack.imgur.com/35i4I.jpg" alt="enter image description here"></a></p>
  
  <p>I should add that the author explains later that <strong>this algorithm doesn't rely on brute force techniques</strong>.</p>
  
  <p><strong>PROBLEMS</strong></p>
  
  <p>As you can see, the explanation is relatively vague and <strong>step 2</strong> is rather unclear (in terms of coding). All I have so far are "pieces of a puzzle":</p>
  
  <ul>
  <li>a "site" (list of selected integers)</li>
  <li>an adjacency matrix (nestled lists)</li>
  <li>"spaces" (dictionnary of lists)</li>
  </ul>
  
  <p>for each unit:</p>
  
  <ul>
  <li>a function that returns its direct neighbors </li>
  <li>a list of its desirable neighbors with their indices in sorted order</li>
  <li><p>a fitness score based on its actual neighbors</p>
  
  <pre><code>from random import shuffle
  
  n_col, n_row = 7, 5
  to_skip = [0, 1, 21, 22, 23, 24, 28, 29, 30, 31]
  site = [i for i in range(n_col * n_row) if i not in to_skip]
  fitness, grid = [[None if i in to_skip else [] for i in range(n_col * n_row)] for e in range(2)]
  
  n = 2
  k = (n_col * n_row) - len(to_skip)
  rsize = 50
  
  #Adjacency matrix
  adm = [[0, 6, 1, 5, 2],
         [6, 0, 1, 4, 0],
         [1, 1, 0, 8, 0],
         [5, 4, 8, 0, 3],
         [2, 0, 0, 3, 0]]
  
  
  spaces = {"office1": [0 for i in range(4)], 
            "office2": [1 for i in range(6)], 
            "office3": [2 for i in range(6)],
            "passage": [3 for i in range(7)],
            "entry": [4 for i in range(2)]}
  
  
  def setup():
      global grid
      size(600, 400, P2D)
      rectMode(CENTER)
      strokeWeight(1.4)
  
      #Shuffle the order for the random placing to come
      shuffle(site)
  
      #Place units randomly within the limits of the site
      i = -1   
      for space in spaces.items():
          for unit in space[1]:    
              i+=1
              grid[site[i]] = unit
  
  
      #For each unit of each space... 
      i = -1   
      for space in spaces.items():
          for unit in space[1]:    
              i+=1
  
              #Get the indices of the its DESIRABLE neighbors in sorted order
              ada = adm[unit]
              sorted_indices = sorted(range(len(ada)), key = ada.__getitem__)[::-1]
  
              #Select indices with positive weight (exluding 0-weight indices)
              pindices = [e for e in sorted_indices if ada[e] &gt; 0] 
  
              #Stores its fitness score (sum of the weight of its REAL neighbors)
              fitness[site[i]] = sum([ada[n] for n in getNeighbors(i) if n in pindices])
  
      print 'Fitness Score:', fitness
  
  def draw():
      background(255)
  
      #Grid's background
      fill(170)
      noStroke()
      rect(width/2 - (rsize/2) , height/2 + rsize/2 + n_row , rsize*n_col, rsize*n_row)
  
  
      #Displaying site (grid cells of all selected units) + units placed randomly
      for i, e in enumerate(grid):
          if isinstance(e, list): pass
          elif e == None: pass
          else:
              fill(50 + (e * 50), 255 - (e * 80), 255 - (e * 50), 180)
              rect(width/2 - (rsize*n_col/2) + (i%n_col * rsize), height/2 + (rsize*n_row/2) + (n_row - ((k+len(to_skip))-(i+1))/n_col * rsize), rsize, rsize)
              fill(0)
              text(e+1, width/2 - (rsize*n_col/2) + (i%n_col * rsize), height/2 + (rsize*n_row/2) + (n_row - ((k+len(to_skip))-(i+1))/n_col * rsize))
  
  
  
  
  def getNeighbors(i):
      neighbors = []
  
      if site[i] &gt; n_col and site[i] &lt; len(grid) - n_col:
          if site[i]%n_col &gt; 0 and site[i]%n_col &lt; n_col - 1:
              if grid[site[i]-1] != None: neighbors.append(grid[site[i]-1])
              if grid[site[i]+1] != None: neighbors.append(grid[site[i]+1])
              if grid[site[i]-n_col] != None: neighbors.append(grid[site[i]-n_col]) 
              if grid[site[i]+n_col] != None: neighbors.append(grid[site[i]+n_col])
  
      if site[i] &lt;= n_col:
          if site[i]%n_col &gt; 0 and site[i]%n_col &lt; n_col - 1:
              if grid[site[i]-1] != None: neighbors.append(grid[site[i]-1])
              if grid[site[i]+1] != None: neighbors.append(grid[site[i]+1])
              if grid[site[i]+n_col] != None: neighbors.append(grid[site[i]+n_col])
  
          if site[i]%n_col == 0:
              if grid[site[i]+1] != None: neighbors.append(grid[site[i]+1])
              if grid[site[i]+n_col] != None: neighbors.append(grid[site[i]+n_col])
  
          if site[i] == n_col-1:
              if grid[site[i]-1] != None: neighbors.append(grid[site[i]-1])
              if grid[site[i]+n_col] != None: neighbors.append(grid[site[i]+n_col])
  
      if site[i] &gt;= len(grid) - n_col:
          if site[i]%n_col &gt; 0 and site[i]%n_col &lt; n_col - 1:
              if grid[site[i]-1] != None: neighbors.append(grid[site[i]-1])
              if grid[site[i]+1] != None: neighbors.append(grid[site[i]+1])
              if grid[site[i]-n_col] != None: neighbors.append(grid[site[i]-n_col])
  
          if site[i]%n_col == 0:
              if grid[site[i]+1] != None: neighbors.append(grid[site[i]+1])
              if grid[site[i]-n_col] != None: neighbors.append(grid[site[i]-n_col])
  
          if site[i]%n_col == n_col-1:
              if grid[site[i]-1] != None: neighbors.append(grid[site[i]-1])
              if grid[site[i]-n_col] != None: neighbors.append(grid[site[i]-n_col])
  
      if site[i]%n_col == 0:
          if site[i] &gt; n_col and site[i] &lt; len(grid) - n_col:
              if grid[site[i]+1] != None: neighbors.append(grid[site[i]+1])
              if grid[site[i]+n_col] != None: neighbors.append(grid[site[i]+n_col])
              if grid[site[i]-n_col] != None: neighbors.append(grid[site[i]-n_col])
  
      if site[i]%n_col == n_col - 1:
          if site[i] &gt; n_col and site[i] &lt; len(grid) - n_col:
              if grid[site[i]-1] != None: neighbors.append(grid[site[i]-1])
              if grid[site[i]+n_col] != None: neighbors.append(grid[site[i]+n_col])
              if grid[site[i]-n_col] != None: neighbors.append(grid[site[i]-n_col])
  
      return neighbors
  </code></pre></li>
  </ul>
  
  <p><a href="https://i.stack.imgur.com/xRN87.png" rel="noreferrer"><img src="https://i.stack.imgur.com/xRN87.png" alt="enter image description here"></a></p>
  
  <p>I would really appreciate if someone could help connect the dots and explain me:</p>
  
  <ul>
  <li><strong>how to re-order the units based on their degree of desirable neighborhood ?</strong></li>
  </ul>
  
  <p><strong>EDIT</strong></p>
  
  <p>As some of you have noticed the algorithm is based on the likelihood that certain spaces (composed of units) are adjacent. The logic would have it then that for each unit to place randomly within the limits of the site:</p>
  
  <ul>
  <li>we check its direct neighbors (up, down, left right) beforehand</li>
  <li>compute a fitness score if at least 2 neighbors. (=sum of the weights of these 2+ neighbors)</li>
  <li>and finally place that unit if the adjacency probability is high</li>
  </ul>
  
  <p>Roughly, it would translate into this:</p>
  
  <pre><code>    i = -1   
      for space in spaces.items():
          for unit in space[1]:    
              i+=1
  
              #Get the indices of the its DESIRABLE neighbors (from the adjacency matrix 'adm') in sorted order
              weights = adm[unit]
              sorted_indices = sorted(range(len(weights)), key = weights.__getitem__)[::-1]
  
              #Select indices with positive weight (exluding 0-weight indices)
              pindices = [e for e in sorted_indices if weights[e] &gt; 0] 
  
  
              #If random grid cell is empty
              if not grid[site[i]]:
  
                  #List of neighbors
                  neighbors = [n for n in getNeighbors(i) if isinstance(n, int)]
  
                  #If no neighbors -&gt; place unit
                  if len(neighbors) == 0:
                      grid[site[i]] = unit 
  
                  #If at least 1 of the neighbors == unit: -&gt; place unit (facilitate grouping)
                  if len(neighbors) &gt; 0 and unit in neighbors:
                      grid[site[i]] = unit  
  
                  #If 2 or 3 neighbors, compute fitness score and place unit if probability is high
                  if len(neighbors) &gt;= 2 and len(neighbors) &lt; 4:
  
                      fscore = sum([weights[n] for n in neighbors if n in pindices]) #cumulative weight of its ACTUAL neighbors
                      count = [1 for t in range(10) if random(sum(weights)) &lt; fscore] #add 1 if fscore higher than a number taken at random between 0 and the cumulative weight of its DESIRABLE neighbors
  
                      if len(count) &gt; 5: 
                          grid[site[i]] = unit
  
                  #If 4 neighbors and high probability, 1 of them must belong to the same space
                  if len(neighbors) &gt; 3:
  
                      fscore = sum([weights[n] for n in neighbors if n in pindices]) #cumulative weight of its ACTUAL neighbors                    
                      count = [1 for t in range(10) if random(sum(weights)) &lt; fscore] #add 1 if fscore higher than a number taken at random between 0 and the cumulative weight of its DESIRABLE neighbors
  
                      if len(count) &gt; 5 and unit in neighbors:                       
                          grid[site[i]] = unit
  
  
              #if random grid cell not empty -&gt; pass
              else: pass
  </code></pre>
  
  <p>Given that a significant part of the units won't be placed on the first run (because of low adjacency probability), we need to iterate over and over until a random distribution where all units can be fitted is found.</p>
  
  <p><a href="https://i.stack.imgur.com/SARen.png" rel="noreferrer"><img src="https://i.stack.imgur.com/SARen.png" alt="enter image description here"></a></p>
  
  <p>After a few thousand iterations a fit is found and all the neighboring requirements are met. </p>
  
  <p><strong>Notice however how this algorithm produces separated groups instead of non-divided and uniform stacks</strong> like in the example provided. I should also add that nearly 5000 iterations is a lot more than the 274 iterations mentioned by Mr. Terzidis in his book.</p>
  
  <p><strong>Questions:</strong></p>
  
  <ul>
  <li>Is there something wrong with the way I'm approaching this algorithm ?</li>
  <li>If no then what implicit condition am I missing ? </li>
  </ul>