Klove et al. proposed permutation codes under Chebyshev distance and iterative encoding and decoding algorithms for the permutation code. In this paper, we introduce a factor graph of the decoding problem for the permutation code. On the factor graph, we propose message-passing algorithms for encoding and decoding. Furthermore, we show that the proposed decoding algorithm realizes optimal MAP decoding while Klove’s decoding is sub-optimal.