Algorithm to find size of T set of
matrices with 0 in nearest neighborhood of all ‘1’ entries
By Nasser Abbasi
3/18/08
Introduction
This is an algorithm developed to solve example 8.2.1 from class lecture notes by Professor W.B. Gearhart of the Mathematics department, California state university, Fullerton.
The algorithm is brute force in nature and is recursive. It simply enumerates over the possible matrices and check if each generated is in T or not.
This algorithm is implemented in Matlab, and example output is shown below for n=2,3, 4.
The algorithm is O(2^(N^2)) and so is really slow. It could be speeded by more efficient data structures, but I think this is an NP problem? (no deterministic polynomial time algorithm possible).
Algorithm
Input: N, an integer, which is the matrix size
Output: M, an integer, which is size of the T set.
-- Generate A=(NxN) matrix with all 1’s
-- Initialize set B which will contain all matrices in T to be the empty set
B=alg(A,B).
-- Alg will return set B of all matrices in T found in A
Return Size(B)
FUNCTION B=alg(A: Matrix, B: set)
Let N be the size of A
FOR i = 1 : N
FOR j = 1 : N
IF (A(i,j) /= 0 )
X=A;
X(i.j)=0;
IF X in T -- check if each ‘1’ in X has ‘0’ nearest neighbours
Add X to set B -- since set, only unique matrices are added to B
ELSE
B=Alg(X,B);
END IF
END IF
END
END
RETURN B
END FUNCTION Alg
Result and output
This table shows the size of T for some values of N
|
N |
Size(T) |
|
2 |
6 |
|
3 |
54 |
|
4 |
|
|
|
|
This below is a result from running the matlab implementation. On the left is the result for N=2, and on the right is the result for N=3 (all the 54 matrices are shown).
Partial Output for N=4
EDU>> B=nmaFindSizeT(4)
[1]
0 0 0
0
0 0 0
0
0 0 0
0
0 0 0
1
[2]
0 0 0
0
0 0 0
0
0 0 0
0
0 0 1
0
[3]
0 0 0
0
0 0 0
0
0 0 0
0
0 1 0
1
[4]
0 0 0
0
0 0 0
0
0 0
0 0
0 1 0
0
[5]
0 0 0
0
0 0 0
0
0 0 0
0
1 0 0
1
[6]
0 0 0
0
0 0 0
0
0 0 0
0
1 0 1
0
[7]
0
0 0 0
0 0 0
0
0 0 0
0
1 0 0
0
[8]
0 0 0
0
0 0 0
0
0 0 0
1
0 0 0
0
[9]
0 0 0
0
0 0 0
0
0 0 0
1
0 0 1
0
[10]
0 0 0
0
0 0 0
0
0 0 0
1
0 1 0
0
[11]
0 0 0
0
0 0 0
0
0 0 0
1
1 0 0 0
[12]
0 0 0
0
0 0 0
0
0 0 0
1
1 0 1
0
[13]
0 0 0
0
0 0 0
0
0 0 1
0
0 0 0
1
[14]
0 0 0
0
0 0 0
0
0 0 1
0
0 0 0
0
[15]
0 0 0
0
0 0 0
0
0 0 1
0
1 0 0
1
[16]
0 0 0
0
0 0 0
0
0 0 1
0
1 0
0 0
[17]
0 0 0
0
0 0 0
0
0 1 0
0
0 0 0
1
[18]
0 0 0
0
0 0 0
0
0 1 0
0
0 0 1
0
[19]
0 0 0
0
0 0 0
0
0 1 0
0
0 0 0
0
[20]
0 0 0
0
0 0 0
0
0 1 0
1
0 0 0
0
[21]
0 0 0
0
0 0 0
0
0 1 0 1
0 0 1
0
[22]
0 0 0
0
0 0 0
0
1 0 0
0
0 0 0
1
[23]
0 0 0
0
0 0 0
0
1 0 0
0
0 0 1
0
[24]
0 0
0 0
0 0 0
0
1 0 0
0
0 1 0
1
[25]
0 0 0
0
0 0 0
0
1 0 0
0
0 1 0
0
[26]
0 0 0
0
0 0 0
0
1 0
0 0
0 0 0
0
[27]
0 0 0
0
0 0 0
0
1 0 0
1
0 0 0
0
[28]
0 0 0
0
0 0 0
0
1 0 0
1
0 0 1
0
[29]
0 0 0
0
0 0 0
0
1 0 0
1
0 1 0
0
[30]
A =
0 0 0
0
0 0 0
0
1 0 1
0
0 0 0
1
[31]
A =
0 0 0
0
0 0
0 0
1 0 1
0
0 0 0
0
[32]
A =
0 0 0
0
0 0 0
1
0 0 0
0
0 0 0
1
[33]
A =
0 0 0
0
0 0 0
1
0 0 0 0
0 0 1
0
[34]
A =
0 0 0
0
0 0 0
1
0 0 0
0
0 1 0
1
[35]
A =
0 0 0
0
0 0 0
1
0 0 0
0
0 1 0
0
[36]
A =
0 0 0
0
0 0 0
1
0 0 0
0
1 0 0
1
[37]
A =
0 0 0
0
0 0 0
1
0 0 0
0
1 0 1
0
[38]
A =
0 0 0
0
0 0
0 1
0 0 0
0
1 0 0
0
[39]
A =
0 0 0
0
0 0 0
1
0 0 0
0
0 0 0
0
[40]
A =
0 0 0
0
0 0 0
1
0 0 1 0
0 0 0
1
[41]
A =
0 0 0
0
0 0 0
1
0 0 1
0
0 0 0
0
[42]
A =
0 0 0
0
0 0 0
1
0 0 1
0
1 0 0
1
[43]
A =
0 0 0
0
0 0 0
1
0 0 1
0
1 0 0
0
[44]
A =
0 0 0
0
0 0 0
1
0 1 0
0
0 0 0
1
[45]
A =
0 0 0
0
0
0 0 1
0 1 0
0
0 0 1
0
[46]
A =
0 0 0
0
0 0 0
1
0 1 0
0
0 0 0
0
[47]
A =
0 0 0
0
0 0 0
1
1 0 0
0
0 0 0
1
[48]
A =
0 0 0
0
0 0 0
1
1 0 0
0
0 0 1
0
[49]
A =
0 0 0
0
0 0 0
1
1 0 0
0
0 1 0
1
[50]
A =
0 0 0
0
0 0 0
1
1 0 0
0
0 1 0
0
[51]
A =
0 0 0
0
0 0 0
1
1 0 0
0
0 0 0
0
[52]
A =
0 0 0
0
0 0 0
1
1 0 1
0
0 0 0
1
[53]
A =
0 0 0
0
0 0 0
1
1 0 1
0
0 0 0
0
[54]
A =
0 0 0
0
0 0 1
0
0 0 0
0
0 0 0
1
[55]
A =
0 0 0
0
0 0 1
0
0 0 0
0
0 0 1
0
[56]
A =
0 0 0
0
0 0 1
0
0 0 0
0
0 1 0
1
[57]
A =
0 0 0
0
0 0 1
0
0 0 0
0
0 1 0
0
[58]
A =
0 0 0
0
0 0 1
0
0 0 0
0
1 0 0
1
[59]
A =
0 0 0
0
0 0 1
0
0 0 0
0
1 0 1
0
[60]
A =
0 0 0
0
0 0 1
0
0 0 0
0
1 0 0
0
[61]
A =
0 0 0
0
0 0 1
0
0 0
0 1
0 0 0
0
[62]
A =
0 0 0
0
0 0 1
0
0 0 0
1
0 0 1
0
[63]
A =
0 0 0
0
0 0 1
0
0 0 0
1
0 1 0 0
[64]
A =
0 0 0
0
0 0 1
0
0 0 0
1
1 0 0
0
[65]
A =
0 0 0
0
0 0 1
0
0 0 0
1
1 0 1
0
[66]
A =
0 0 0 0
0 0 1
0
0 0 0
0
0 0 0
0
[67]
A =
0 0 0
0
0 0 1
0
1 0 0
0
0 0 0
1
[68]
A =
0 0 0
0
0 0 1
0
1 0
0 0
0 0 1
0
[69]
A =
0 0 0
0
0 0 1
0
1 0 0
0
0 1 0
1
[70]
A =
0 0 0
0
0 0 1
0
1 0 0
0
0 1 0 0
[71]
A =
0 0 0
0
0 0 1
0
1 0 0
0
0 0 0
0
[72]
A =
0 0 0
0
0 0 1
0
1 0 0
1
0 0 0
0
[73]
A =
0 0 0
0
0 0 1
0
1 0 0
1
0 0 1
0
[74]
A =
0 0 0
0
0 0 1
0
1 0 0
1
0 1 0
0
[75]
A =
0 0 0
0
0 1 0
0
0
0 0 0
0 0 0
1
[76]
A =
0 0 0
0
0 1 0
0
0 0 0
0
0 0 1
0
[77]
A =
0 0 0
0
0 1 0
0
0 0 0
0
0 1 0 1
[78]
A =
0 0 0
0
0 1 0
0
0 0 0
0
0 1 0
0
[79]
A =
0 0 0
0
0 1 0
0
0 0 0
0
1 0 0
1
[80]
A =
0 0 0 0
0 1 0
0
0 0 0
0
1 0 1
0
[81]
A =
0 0 0
0
0 1 0
0
0 0 0
0
1 0 0
0
[82]
A =
0 0 0
0
0 1 0
0
0
0 0 1
0 0 0
0
[83]
A =
0 0 0
0
0 1 0
0
0 0 0
1
0 0 1
0
[84]
A =
0 0 0
0
0 1 0
0
0 0 0
1
0 1 0
0
[85]
A =
0 0 0
0
0 1 0
0
0 0 0
1
1 0 0
0
[86]
A =
0 0 0
0
0 1 0
0
0 0 0
1
1 0 1
0
[87]
A =
0 0 0
0
0 1 0
0
0 0 1
0
0 0 0
1
[88]
A =
0 0 0
0
0 1 0
0
0 0 1
0
0 0 0
0
[89]
A =
0 0 0
0
0 1 0
0
0 0 1
0
1 0 0
1
[90]
A =
0 0 0
0
0 1 0
0
0 0 1
0
1 0 0
0
[91]
A =
0 0 0
0
0 1 0
0
0 0 0
0
0 0
0 0
[92]
A =
0 0 0
0
0 1 0
1
0 0 0
0
0 0 0
1
[93]
A =
0 0 0
0
0 1 0
1
0 0 0
0
0 0 1
0
[94]
A =
0 0
0 0
0 1 0
1
0 0 0
0
0 1 0
1
[95]
A =
0 0 0
0
0 1 0
1
0 0 0
0
0 1 0
0
[96]
A =
0 0 0
0
0 1 0 1
0 0 0
0
1 0 0
1
[97]
A =
0 0 0
0
0 1 0
1
0 0 0
0
1 0 1
0
[98]
A =
0 0 0
0
0 1 0
1
0 0 0
0
1 0
0 0
[99]
A =
0 0 0
0
0 1 0
1
0 0 0
0
0 0 0
0
[100]
A =
0 0 0
0
0 1 0
1
0 0 1
0
0 0 0
1
[101]
A =
0
0 0 0
0 1 0
1
0 0 1
0
0 0 0
0
[102]
A =
0 0 0
0
0 1 0
1
0 0 1
0
1 0 0
1
[103]
A =
0 0 0
0
0 1 0
1
0 0 1
0
1 0 0
0
[104]
A =
0 0 0
0
1 0 0
0
0 0 0
0
0 0 0
1
[105]
A =
0 0 0
0
1 0 0
0
0 0 0
0
0 0 1
0
[106]
A =
0 0 0
0
1 0 0
0
0 0 0
0
0 1 0
1
[107]
A =
0 0 0
0
1 0 0
0
0 0 0
0
0 1 0
0
[108]
A =
0 0 0
0
1 0 0
0
0 0 0
0
1 0 0
1
[109]
A =
0 0 0
0
1 0 0
0
0 0 0
0
1 0 1
0
[110]
A =
0 0 0
0
1
0 0 0
0 0 0
0
1 0 0
0
[111]
A =
0 0 0
0
1 0 0
0
0 0 0
1
0 0 0
0
[112]
A =
0 0 0
0
1 0 0
0
0 0 0
1
0 0 1
0
[113]
A =
0 0 0
0
1 0 0
0
0 0 0
1
0 1 0
0
[114]
A =
0 0 0
0
1 0 0
0
0 0 0
1
1 0 0 0
[115]
A =
0 0 0
0
1 0 0
0
0 0 0
1
1 0 1
0
[116]
A =
0 0 0
0
1 0 0
0
0 0 1
0
0 0 0
1
[117]
A =
0 0 0 0
1 0 0
0
0 0 1
0
0 0 0
0
[118]
A =
0 0 0
0
1 0 0
0
0 0 1
0
1 0 0
1
[119]
A =
0 0 0
0
1 0 0
0
0
0 1 0
1 0 0
0
[120]
A =
0 0 0
0
1 0 0
0
0 1 0
0
0 0 0
1
[121]
A =
0 0 0
0
1 0 0
0
0 1 0
0
0 0 1
0
[122]
A =
0 0 0
0
1 0 0
0
0 1 0
0
0 0 0
0
[123]
A =
0 0 0
0
1 0 0
0
0 1 0
1
0 0 0
0
[124]
A =
0 0
0 0
1 0 0
0
0 1 0
1
0 0 1
0
[125]
A =
0 0 0
0
1 0 0
0
0 0 0
0
0 0 0
0
[126]
A =
0 0 0
0
1 0 0 1
0 0 0
0
0 0 0
1
[127]
A =
0 0 0
0
1 0 0
1
0 0 0
0
0 0 1
0
[128]
A =
0 0 0
0
1 0 0
1
0 0 0
0
0
1 0 1
[129]
A =
0 0 0
0
1 0 0
1
0 0 0
0
0 1 0
0
[130]
A =
0 0 0
0
1 0 0
1
0 0 0
0
1 0 0
1
[131]
A =
0 0 0
0
1 0 0
1
0 0 0
0
1 0 1
0
[132]
A =
0 0 0
0
1 0 0
1
0 0 0
0
1 0 0
0
[133]
A =
0 0 0
0
1 0
0 1
0 0 0
0
0 0 0
0
[134]
A =
0 0 0
0
1 0 0
1
0 0 1
0
0 0 0
1
[135]
A =
0 0 0
0
1 0 0
1
0 0 1 0
0 0 0
0
[136]
A =
0 0 0
0
1 0 0
1
0 0 1
0
1 0 0
1
[137]
A =
0 0 0
0
1 0 0
1
0 0 1
0
1 0 0
0
[138]
A =
0 0 0
0
1 0 0
1
0 1 0
0
0 0 0
1
[139]
A =
0 0 0
0
1 0 0
1
0 1 0
0
0 0 1
0
[140]
A =
0 0 0
0
1 0 0
1
0 1 0
0
0 0 0
0
[141]
A =
0 0 0
0
1 0 1
0
0 0 0
0
0 0 0
1
[142]
A =
0 0 0
0
1 0 1
0
0 0
0 0
0 0 1
0
[143]
A =
0 0 0
0
1 0 1
0
0 0 0
0
0 1 0
1
[144]
A =
0 0 0
0
1 0 1
0
0 0 0
0
0 1 0 0
[145]
A =
0 0 0
0
1 0 1
0
0 0 0
0
1 0 0
1
[146]
A =
0 0 0
0
1 0 1
0
0 0 0
0
1 0 1
0
[147]
A =
0 0 0
0
1 0 1
0
0 0 0
0
1 0 0
0
[148]
A =
0 0 0
0
1 0 1
0
0 0 0
1
0 0 0
0
[149]
A =
0 0 0
0
1 0 1
0
0 0 0
1
0 0 1
0
[150]
A =
0 0 0
0
1 0 1
0
0 0 0
1
0 1 0
0
[151]
A =
0 0 0
0
1 0 1
0
0 0 0
1
1 0
0 0
[152]
A =
0 0 0
0
1 0 1
0
0 0 0
1
1 0 1
0
[153]
A =
0 0 0
0
1 0 1
0
0 0 0
0
0 0 0
0
[154]
A =
0 0
0 1
0 0 0
0
0 0 0
0
0 0 0
1
[155]
A =
0 0 0
1
0 0 0
0
0 0 0
0
0 0 1
0
[156]
A =
0 0 0
1
0 0 0 0
0 0 0
0
0 1 0
1
[157]
A =
0 0 0
1
0 0 0
0
0 0 0
0
0 1 0
0
[158]
A =
0 0 0
1
0 0 0
0
0 0 0
0
1 0 0
1
[159]
A =
0 0 0
1
0 0 0
0
0 0 0
0
1 0 1
0
[160]
A =
0 0 0
1
0 0 0
0
0 0 0
0
1 0 0
0
[161]
A =
0 0 0
1
0 0 0
0
0 0 0
1
0 0 0
0
[162]
A =
0 0 0
1
0 0 0
0
0 0 0
1
0 0 1
0
[163]
A =
0 0 0
1
0 0
0 0
0 0 0
1
0 1 0
0
[164]
A =
0 0 0
1
0 0 0
0
0 0 0
1
1 0 0
0
[165]
A =
0 0 0
1
0 0 0
0
0 0 0
1
1 0 1
0
[166]
A =
0 0 0
1
0 0 0
0
0 0 1
0
0 0 0
1
[167]
A =
0 0 0
1
0 0 0
0
0 0 1
0
0 0 0
0
[168]
A =
0 0 0
1
0 0 0
0
0 0 1
0
1 0 0
1
[169]
A =
0 0 0
1
0 0 0
0
0 0 1
0
1 0 0
0
[170]
A =
0 0 0 1
0 0 0
0
0 1 0
0
0 0 0
1
[171]
A =
0 0 0
1
0 0 0
0
0 1 0
0
0 0 1
0
[172]
A =
0 0 0
1
0 0 0
0
0
1 0 0
0 0 0
0
[173]
A =
0 0 0
1
0 0 0
0
0 1 0
1
0 0 0
0
[174]
A =
0 0 0
1
0 0 0
0
0 1 0
1
0 0 1
0
[175]
A =
0 0 0
1
0 0 0
0
1 0 0
0
0 0 0
1
[176]
A =
0 0 0
1
0 0 0
0
1 0 0
0
0 0 1
0
[177]
A =
0 0
0 1
0 0 0
0
1 0 0
0
0 1 0
1
[178]
A =
0 0 0
1
0 0 0
0
1 0 0
0
0 1 0
0
[179]
A =
0 0 0
1
0 0 0 0
1 0 0
0
0 0 0
0
[180]
A =
0 0 0
1
0 0 0
0
1 0 0
1
0 0 0
0
[181]
A =
0 0 0
1
0 0 0
0
1 0 0
1
0
0 1 0
[182]
A =
0 0 0
1
0 0 0
0
1 0 0
1
0 1 0
0
[183]
A =
0 0 0
1
0 0 0
0
1 0 1
0
0 0 0
1
[184]
A =
0 0 0
1
0 0 0
0
1 0 1
0
0 0 0
0
[185]
A =
0 0 0
1
0 0 0
0
0 0 0
0
0 0 0
0
[186]
A =
0 0 0
1
0 0
1 0
0 0 0
0
0 0 0
1
[187]
A =
0 0 0
1
0 0 1
0
0 0 0
0
0 0 1
0
[188]
A =
0 0 0
1
0 0 1
0
0 0 0
0
0 1 0
1
[189]
A =
0 0 0
1
0 0 1
0
0 0 0
0
0 1 0
0
[190]
A =
0 0 0
1
0 0 1
0
0 0 0
0
1 0 0
1
[191]
A =
0 0 0
1
0 0 1
0
0 0 0
0
1 0 1
0
[192]
A =
0 0 0
1
0 0 1
0
0 0 0
0
1 0 0
0
[193]
A =
0 0 0
1
0 0 1
0
0 0 0
1
0 0 0
0
[194]
A =
0 0 0
1
0 0 1
0
0 0 0
1
0 0 1
0
[195]
A =
0 0 0
1
0 0 1
0
0 0
0 1
0 1 0
0
[196]
A =
0 0 0
1
0 0 1
0
0 0 0
1
1 0 0
0
[197]
A =
0 0 0
1
0 0 1
0
0 0 0
1
1 0 1 0
[198]
A =
0 0 0
1
0 0 1
0
0 0 0
0
0 0 0
0
[199]
A =
0 0 0
1
0 0 1
0
1 0 0
0
0 0 0
1
[200]
A =
0 0 0
1
0 0 1
0
1 0 0
0
0 0 1
0
[201]
A =
0 0 0
1
0 0 1
0
1 0 0
0
0 1 0
1
[202]
A =
0 0 0
1
0 0 1
0
1 0 0
0
0 1 0
0
[203]
A =
0 0 0
1
0 0 1
0
1 0 0
0
0 0 0
0
[204]
A =
0 0 0
1
0 0 1
0
1 0 0
1
0 0
0 0
[205]
A =
0 0 0
1
0 0 1
0
1 0 0
1
0 0 1
0
[206]
A =
0 0 0
1
0 0 1
0
1 0 0
1
0 1 0
0
[207]
A =
0 0
0 1
0 1 0
0
0 0 0
0
0 0 0
1
[208]
A =
0 0 0
1
0 1 0
0
0 0 0
0
0 0 1
0
[209]
A =
0 0 0
1
0 1 0
0
0 0 0
0
0 1 0
1
[210]
A =
0 0 0
1
0 1 0
0
0 0 0
0
0 1 0
0
[211]
A =
0 0 0
1
0 1 0
0
0 0 0
0
1
0 0 1
[212]
A =
0 0 0
1
0 1 0
0
0 0 0
0
1 0 1
0
[213]
A =
0 0 0
1
0 1 0
0
0 0 0
0
1 0 0
0
[214]
A =
0
0 0 1
0 1 0
0
0 0 0
1
0 0 0
0
[215]
A =
0 0 0
1
0 1 0
0
0 0 0
1
0 0 1
0
[216]
A =
0 0 0
1
0 1 0
0
0 0 0
1
0 1 0
0
[217]
A =
0 0 0
1
0 1 0
0
0 0 0
1
1 0 0
0
[218]
A =
0 0 0
1
0 1 0
0
0 0 0 1
1 0 1
0
[219]
A =
0 0 0
1
0 1 0
0
0 0 1
0
0 0 0
1
[220]
A =
0 0 0
1
0 1 0
0
0 0 1
0
0 0 0
0
[221]
A =
0 0 0
1
0 1 0
0
0 0 1
0
1 0 0
1
[222]
A =
0 0 0
1
0 1 0
0
0 0 1
0
1 0 0
0
[223]
A =
0 0 0
1
0
1 0 0
0 0 0
0
0 0 0
0
[224]
A =
0 0 0
1
1 0 0
0
0 0 0
0
0 0 0
1
[225]
A =
0 0 0
1
1 0 0
0
0 0 0
0
0 0 1
0
[226]
A =
0 0 0
1
1 0 0
0
0 0 0
0
0 1 0
1
[227]
A =
0 0 0
1
1 0 0
0
0 0 0
0
0 1 0
0
[228]
A =
0 0 0
1
1 0 0
0
0 0 0
0
1 0 0
1
[229]
A =
0 0 0
1
1 0 0
0
0 0 0
0
1 0 1
0
[230]
A =
0 0 0 1
1 0 0
0
0 0 0
0
1 0 0
0
[231]
A =
0 0 0
1
1 0 0
0
0 0 0
1
0 0 0
0
[232]
A =
0 0 0
1
1 0 0
0
0 0 0
1
0 0 1
0
[233]
A =
0 0 0
1
1 0 0
0
0 0 0
1
0 1 0
0
[234]
A =
0 0 0
1
1 0 0
0
0 0 0
1
1 0
0 0
[235]
A =
0 0 0
1
1 0 0
0
0 0 0
1
1 0 1
0
[236]
A =
0 0 0
1
1 0 0
0
0 0 1
0
0 0 0
1
[237]
A =
0 0 0
1
1 0 0
0
0 0 1
0
0 0 0
0
[238]
A =
0 0 0
1
1 0 0
0
0 0 1
0
1 0 0
1
[239]
A =
0 0 0
1
1 0
0 0
0 0 1
0
1 0 0
0
[240]
A =
0 0 0
1
1 0 0
0
0 1 0
0
0 0 0
1
[241]
A =
0 0 0
1
1 0 0
0
0 1 0
0
0 0 1
0
[242]
A =
0 0 0
1
1 0 0
0
0 1 0
0
0 0 0
0
[243]
A =
0 0 0
1
1 0 0
0
0 1 0
1
0 0 0
0
[244]
A =
0 0 0
1
1 0 0
0
0 1 0
1
0 0 1
0
[245]
A =
0 0 0
1
1 0 0
0
0 0 0
0
0 0 0
0