We present a Hamilton cycle in the k-sided pancake network and four different combinatorial algorithms to traverse the cycle. The vertices in the network are coloured permutations pi = p_1 p_2 ... p_n where each element p_i has an associated colour from the set {0,1,2,...,k-1}. There is a directed edge (pi_1,pi_2) if pi_2 can be obtained from pi_1 by a ``flip'' of size j which is a prefix reversal of the first j elements that also increments the colours of the flipped elements taken modulo k. When k=1 the network is known as the pancake network, and when k=2, the network is known as the burnt-pancake network. We generalize known results for these special cases by applying a greedy min-flip strategy to obtain a Hamilton cycle in the k-sided pancake network. Such a cycle corresponds to a cyclic Gray code of coloured permutations where successive permutations differ by a single flip. A recursive construction enables the Hamilton cycle to be traversed in O(1)-amortized time per permutation and a loop-free algorithm is provided to list the sequence of flip-sizes by applying the recursive definition. An O(n)-time successor rule is also presented to determine the successor of a given permutation in the cycle, allowing for the cycle to be traversed by starting with any arbitrary permutation. Interestingly, a greedy max-flip strategy that works for the pancake and burnt pancake networks does not generalize to the k-sided pancake network.

https://link.springer.com/chapter/10.1007/978-3-030-79987-8_10