From InterSciWiki

Contents 1 Purpose 2 Defining avoidant permutation 3 Uniform probability 4 Example 5 A fast algorithm 6 R test code 6.1 #step 2 6.2 #step 3 6.3 #FROM MAIN PROGRAM 6.4 #step 4

[edit] Purpose

There are many problems for which a permutation is required that avoids certain outcomes. An example is the permutation of either women's or men's marriages within a specified generation, avoiding marriages between siblings.

[edit] Defining avoidant permutation

REPLACE WITH:

Avoidant permutation considers a vector of integers a0 (fixed parent "fathers") with values that must be avoided in permuting f1 (varying parent "mothers" of f0 "children"). Say a0={1 2 4} "fathers" and f1={4 5 6} "mothers" for f0={7 8 9} "children". Then an acceptable permutation of f1 is f2={6 4 5} but not f2={6 5 4} because the third element of f0 and f2 are equal. Let N be the number of elements in f0 and f1, with some f0=0 elements but no f1=0 elements.

NOT RIGHT:

Avoidant permutation considers a vector of integers f0 with values that must be avoided in permuting f1. Say f0={1 2 4} and f1={4 5 6}. Then an acceptable permutation of f1 is f2={6 4 5} but not f2={6 5 4} because the third element of f0 and f2 are equal. Let N be the number of elements in f0 and f1, with some f0=0 elements but no f1=0 elements.

[edit] Uniform probability

All possible outcomes under the avoidance constraint must be equiprobable. The default is to permute all, then select those that violate their avoidance constraints and permute them. Another option is to first permute all those without an avoidance constraint and then permute those that do.

[edit] Example

For example, in the default, let f2=permute(f1), and count F=the number of forbidden values where elements in the f0,f2 arrays are equal.

1. If F=0, accept f2.
2. Else, accept up to N-2 elements in f2 that are not excluded. (This leaves k=2 or more elements to exclude in f2, including all those that are forbidden because they are in f0.) Permute the remaining elements, repeating the test for exclusion. This will converge.

[edit] A fast algorithm

REPLLACE WITH:

1. (Default: Skip for alternative). Permute f1 Mo. Reorder a0 Fa and f0 Ch accordingly. Do by binding.
2. Create an s1={0/1 array} of length N where the 1s correspond to elements in f1 that have matching values in a0.
3. Reorder fF0=f0,fF1=f1,aA0=a0ms1 uniformly so that the ones in s1 are trailing. Let be the first M zero elements in s1.
4. For the M first elements in s1, NEW MO f2(1:M)=permute(fF1(1:M)).
5. Then permute f2=fF1(M+1:N) and the matching aA0 and fF0 fF1 until the latter pair have no ordered pair of the same values.

NOT:

1. (Default: Skip for alternative). Permute f1. Reorder f0 accordingly. Do by binding.
2. Create an s1={0/1 array} of length N where the 1s correspond to elements in f1 that have matching values in f0.
3. Reorder fF0=f0,fF1=f1,s1 uniformly so that the ones in s1 are trailing. Let be the first M zero elements in s1.
4. For the M first elements in s1, f2(1:M)=permute(ff1(1:M)).
5. Then permute fF2=f2(M+1:N) and the matching fF0 and fF1 until the latter pair have no ordered pair of the same values.

[edit] R test code

#case 2 has 2 or more constraints
f0=c(1,2,3,4) #father numbers for nodes 7,4,6,5
f1=c(3,4,6,5) #permute these without "4" landing in position 4, i.e., 6,7,4,5 is ok
#case 1 has 1 constraint
f0=c(1,2,3,4) #father numbers for CHILD nodes 7,4,6,5
f1=c(7,4,6,5) #permute these without "4" landing in position 4, i.e., 6,7,4,5 is ok
#case 0 ---- REAL DATA
f0=fj  #MOther FJ numbers for CHILD nodes F1 (FATHERS REMAIN CONSTANT)
f0
f1     #CHILD NODES with the mother
a0     #FATHERS TO AVOID - don't change
N=length(f1)
#step 1 permute the cols of dp
p1=permute(f1)
p1
d <- data.frame(cbind(f1,p1,f0))
d
td=t(d)
td
dp=permute(td)
dp
p0=0
reord=0   #d[i,j]=row i col j
for(i in 1:N) {
 for(j in 1:N){
 if (d[i,1]==d[j,2]) {reord[i]=j;
  p0[j]=f0[i]}
}}
d <- data.frame(cbind(f1,p1,f0,p0,reord))
d
#Now p0/p1 have replaced f0/f1
#f0=p0
#f1=p1
#f0
#f1
d <- data.frame(cbind(f1,p1,f0))
d

[edit] #step 2

s1=f0 
for(k in 1:n) s1[k] <- 0
for(i in 1:N) {
for(k in 1:N) if (f0[i]==f1[k]) s1[k] <- 1 else s1[k] <- 0
}
s1 #returns ones in the f1 array position for values in f0
f0
f1
d <- data.frame(cbind(f1,f0))
d

[edit] #step 3

#step 3: take out and permute the no avoidance elements
#which(s1==0) #returns indices of x1 where x1==a1  1,3,4
#which(s1==1) #returns indices of x1 where x1==a1  2nd item cannot go to position 4
fF1=0
index=0
for(k in 1:N) if (s1[k]==0) {
  index=index+1
  fF1[index]=f1[k]
} 
fF1
M=N-index
fF1=fF1(1,index-1)
fF1
fF1=permute(fF1) #permute these
fF1
F1=0
if (M==1) F1[1:index-1]=fF1[1:index-1] else F1[1:index]=fF1[1:index]
F1
if (M==1) {M=2 #IN THIS CASE PUT TRAILING ELEMENT IN SECOND SET
 F1[index]=999}
index=N-M
M
index
idx=index
for(k in 1:N) if (s1[k]==1) {
  idx=idx+1
  fF1[idx]=f1[k]
}
for(i in index+1:N) if (M==2) F1[i]=fF1[i]
F1  #permuted fathers

[edit] #FROM MAIN PROGRAM

f2 <- permute(F1)
f2 #these are the permuted-i locations
#permutation created for columns
numnodes
##CREATE NEW NETWORK
#delete the old ties of type 2
for (i in 1:lensqrt) {#1
 for (j in 1:lensqrt) {#2
                      if (v1[i]==igen & n2[i,j]==2) m2[i,j] <- 0
 }#2
}#1
 #create permuted tie as type 2 #3
 #for (i in 1:num) m2[f2[i],fj[i]] <- 2 #3 ####NOT THE RIGHT ROW AND COLUMN?
 for (i in 1:num) m2[fj[i],f2[i]] <- 2 #3 #IS THIS RIGHT FOR ROW AND COLUMN?
m3=m2
gplot(m3,  coord = cbind(4*v2,4-v1),gmode = "digraph", vertex.col=v1, edge.col=c(1,2), vertex.cex=2,label = c(1:dim(m3)[2])) #mode = coord, label = c(1:dim(m3)[2]),
#gplot(m3,  coord = cbind(4*v2,4-v1),gmode = "digraph", vertex.col=v1, vertex.cex=2) #mode = coord
#}#0
size=length(n1)^.5
size
matrix(n1,size,size)
matrix(m3,size,size)

[edit] #step 4

#now permute (don't rotate) the remaining items until satisfactory
for(i=1:M)

F3=0
F3=f2
f2 <- permute(f1) ########permute and permute list
#PREVENT CASE WHERE male(element in f2) has parent n1(
for (k in 1:Len1) {
}
}
f2

Back to Software: Kinship simulation#Permutation