To be a valid permutation you also must not have repeated values.
Metropolis will be incredibly inneficient because everything has to go right for it to propose different valid permutations.
I am conviced you need a custom step sampler. This would actually be a nice addition to PyMC.
The integer check shouldn’t be needed. I think PyMC knows this is a discrete variable in this case and will only propose discrete values. Worth printing value.dtype in the logp function to check.
On the shape thing, I am not sure what is your confusion, so at the risk of not helping at all I suggest you have a look at Distribution Dimensionality — PyMC 5.6.0 documentation