#StackBounty: #python #processing #permutation How to use permutation to re-order units based on their degree of desirable neighborhood…

Bounty: 50

I would need help to implement a permutation algorithm allowing the generation of building plans, that I’ve recently stumbled on while reading Professor Kostas Terzidis’ latest publication: Permutation Design: Buildings, Texts and Contexts (2014).

CONTEXT

  • Consider a site (b) that is divided into a grid system (a).
  • 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)

enter image description here

Quoting Prof. Terzidis:

“A way of solving this problem is to stochastically place spaces within the grid until all spaces are fit and the constraints are satisfied”

The figure above shows such a problem and a sample solution (f).

ALGORITHM (as briefly described in the book)

1/ “Each space is associated with a list that contains all other spaces sorted according to their degree of desirable neighborhood.”

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)”

Example of nine randomly generated plans:

enter image description here

I should add that the author explains later that this algorithm doesn’t rely on brute force techniques.

PROBLEMS

As you can see, the explanation is relatively vague and step 2 is rather unclear (in terms of coding). All I have so far are “pieces of a puzzle”. On one hand:

  • a “site” (list of selected integers)
  • an adjacency matrix (nestled lists)
  • “spaces” (dictionnary of lists)
    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]
    
    #Makes a copy of "site" and shuffle its order for future random placing
    ssite = site; shuffle(ssite)
    
    n = 2
    k = (n_col * n_row) - len(to_skip)
    rsize = 30
    
    #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": [1 for i in range(4)], 
              "office2": [2 for i in range(6)], 
              "office3": [3 for i in range(6)],
              "passage": [4 for i in range(7)],
              "entry": [5 for i in range(2)]}
    
    def setup():
        size(600, 400, P2D)
        background(255)
        rectMode(CENTER)
    
        #Grid's background
        fill(70)
        rect(width/2 - (rsize/2) , height/2 + rsize/2 + n_row , rsize*n_col, rsize*n_row)
    
        #Displaying site (all selected units)
        fill(255)
        for i in site:
            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)
    
    
        #For each unit in each space...
        i = -1
        fill(0)
        for space in spaces.items():
            for unit in space[1]:
    
                i+=1
    
                #get the indices of its desired neighbors in sorted order
                ada = adm[unit-1]
                sorted_indices = sorted(range(len(ada)), key = lambda k: ada[k])[::-1]
    
                #place each unit number randomly in the site
                text(unit, width/2 - (rsize*n_col/2) + (ssite[i]%n_col * rsize), height/2 + (rsize*n_row/2) + (n_row - ((k+len(to_skip))-(ssite[i]+1))/n_col * rsize))
    

enter image description here

And on the other hand:

  • a simple permutation algorithm
    rsize = 60
    n_col, n_row = (4, 3)
    n, k = 2, int(n_col * n_row)
    bits = [[] for i in range(int(pow(n, k)))]
    
    
    def setup():
        size(700, 400, P2D)
    
        for i in range(int(pow(n, k))):
            for j in range(k):
                bit = i / int(pow(n, k - j - 1)) % n + 1
                bits[i].append(bit)
    
    
    def draw():
        background(255)
    
        for i in range(k):
            bit = bits[frameCount % len(bits)][i]
            if bit == 1: fill(0)
            if bit == 2: fill(255, 0, 0)
    
    
            rect(width / 2 - rsize * n_col / 2 + i % n_col * rsize, height
                 / 2 + rsize * n_row / 2 + n_row - (k - (i + 1)) / n_col
                 * rsize, rsize, rsize)
    
            fill(0)
            text(bit - 1, 60 + i * 8, 20)
    
        text('GENE:', 20, 20)
        text(u'NO.', 20, 40)
        text(frameCount, 45, 40)
        text('Remaining', 20, 60)
        text(len(bits) - frameCount, 90, 60)
    
        if frameCount == len(bits): noLoop()
    

enter image description here

I would really appreciate if someone could help connect the dots and explain me:

  • how to re-order the units based on their degree of desirable neighborhood ?
  • how is it related to permutation ?


Get this bounty!!!

#StackBounty: #hypothesis-testing #p-value #permutation-test #permutation How is the exact permutation test procedure carried out: iter…

Bounty: 150

I’ve tried to find an article that explains the procedure of permutation tests for the exhaustive sampling of all permutations (not the monte carlo method) and couldn’t find a resource that was specific enough to help me with the ambiguity outlined below. For example, the Wikipedia article (https://en.wikipedia.org/wiki/Resampling_(statistics)#Permutation_tests) says

enter image description here

For example, given a combined dataset (1, 2, 3) where group A has length 2 and group B has length 1 for simplicity, it is not clear to me whether “all possible ways to divide it” means {(1, 2), (3)} and {(2, 1), (3), …} or if they count “{(1, 2), (3)}” and “{(2, 1), (3)}” as the same division.

Looking at various code examples, for example, the Python, R, Julia, etc. examples on https://rosettacode.org/wiki/Permutation_test, I see that the permutation test is usually implemented as follows:


Given two samples A and B

  1. Record the test statistic (e.g., $|bar{A} – bar{B}|$)
  2. Combine samples A and B into one large sample AB
  3. for combination of length(A) from AB:
    3a) compute permutation statistic (e.g., $|bar{A’} – bar{B’}|$, where A’ is the combination from 3. and B’ are all the samples in AB that are not in A’).
    3b) record permutation statistic
  4. Compute p-value as the proportion the permutation statistic from 3a) was more extreme than the test statistic from 1. divided by the number of combinations sampled

However, shouldn’t we be sampling the permutations instead of combinations of length A? For example, as outlined below (I highlighted the difference to the previous procedure in bold):


Given two samples A and B

  1. Record the test statistic (e.g., $|bar{A} – bar{B}|$)
  2. Combine samples A and B into one large sample AB
  3. for permutation of length(AB) from AB:
    3a) compute permutation statistic (e.g., $|bar{A’} – bar{B’}|$, where A’ are the first len(A) samples in the permuted AB sequence and B’ are the remaining samples in AB

  4. Compute p-value as the proportion the permutation statistic from 3a) was more extreme than the test statistic from 1. divided by the number of permutations sampled


Or, to provide a simple numeric example, consider the following 2 samples

a = [1, 3]
b = [2]

with the observed difference:
obs = |mean(a) – mean(b)| = 2

Using the “combinations” procedure, we would be sampling the following:

(1, 2), (3) => diff 0
(1, 3), (2) => diff 2
(2, 3), (1) => diff 4

where in 2 out of 3 cases, we would observe a difference equal or more extreme than in the observed statistic (i.e., p=2/3)

Now, using permutations, we would get the following:

(1, 2), (3) => diff 0
(1, 3), (2) => diff 2
(2, 1), (3) => diff 0
(2, 3), (1) => diff 4
(3, 1), (2) => diff 2
(3, 2), (1) => diff 4

Here, we observe a difference that is equal or more extreme than the observed statistic in 4 out of 6 cases (p=4/6)

Does anyone no more about the exact procedure and has a reliable resource at hand? Thanks!


Get this bounty!!!