We completely determine the localized automorphisms of the Cuntz algebras O_n corresponding to permutation matrices in M_n ⊗ M_n for n=3 and n=4. This result is obtained through a combination of general combinatorial techniques and large scale computer calculations. Our analysis proceeds according to the general scheme proposed in a previous paper, where we analyzed in detail the case of O₂ using labeled rooted trees. We also discuss those proper endomorphisms of these Cuntz algebras which restrict to automorphisms of their respective diagonals. In the case of O₃ we compute the number of automorphisms of the diagonal induced by permutation matrices in M₃ ⊗ M₃ ⊗ M₃.