A ‘Hot Potato’ Gray Code for Permutations

We give the n! permutations of [n]={1,2,…,n} a cyclic order inspired by the childrenʼs game of Hot Potato. Our order is a transposition Gray code, meaning that consecutive permutations differ by a single transposition. Furthermore, each transposition is restricted in two ways: (1) It must transpose value n (the “hot potato”); (2) It must transpose positions that are circularly adjacent or semi-adjacent. In other words, if each permutation is written circularly, then our order repeatedly transposes the value n with a value that is one or two positions to its left or right.