CF 103586A - Robot Production
A signed permutation of ${1,2,dots,n}$ is a sequence $(a1,dots,an)$ in which ${ The goal is to construct a Hamiltonian path in the graph whose vertices are signed permutations and whose edges correspond exactly to these two operations.
Rating: -
Tags: -
Solve time: 2m 8s
Verified: no
Solution
Solution
A signed permutation of ${1,2,\dots,n}$ is a sequence $(a_1,\dots,a_n)$ in which ${|a_1|,\dots,|a_n|}$ is a permutation of ${1,\dots,n}$ and each $a_i$ carries an independent sign. The required moves are adjacent swaps $a_i \leftrightarrow a_{i+1}$ and negation of $a_1$.
The goal is to construct a Hamiltonian path in the graph whose vertices are signed permutations and whose edges correspond exactly to these two operations.
The construction follows the structure of Algorithm P (plain changes) for permutations, with a controlled rule for sign changes that guarantees that every sign flip is executed only when the affected element is at position $1$.
Let $(a_1,\dots,a_n)$ be the current signed permutation. Maintain an auxiliary direction array $o_1,\dots,o_n$ as in Algorithm P, which drives adjacent swaps of elements in the underlying permutation. Ignore signs when computing the swap structure; the swaps are exactly those of Algorithm P applied to the underlying absolute values.
Additionally maintain a second state variable $b_i \in {0,1}$ for each element $i$, representing whether the current sign of $i$ is positive ($0$) or negative ($1$). The evolution rule for signs is synchronized with the permutation motion as follows.
Whenever an element $x$ arrives at position $1$ as a result of an adjacent interchange, perform the operation $a_1 \leftarrow -a_1$, which toggles $b_x$. This is always legal because it is exactly the allowed operation “negate the first element”. No other sign changes are ever performed.
The algorithm proceeds exactly as Algorithm P on the underlying permutation structure: at every step it performs one adjacent interchange determined by the $c_j,o_j$ mechanism of Algorithm P, and between such interchanges it applies no additional changes except the forced negation triggered when a new element becomes first.
Correctness of adjacency follows because every transition is either an adjacent swap or a negation of the first element by construction.
It remains to show that every signed permutation is generated exactly once. The underlying absolute values follow Algorithm P, which generates all $n!$ permutations exactly once in a Hamiltonian cycle. Fix any underlying permutation $\pi$. Each time an element $x$ enters position $1$ during the evolution of Algorithm P, the rule flips the sign of $x$. The element $x$ enters position $1$ exactly once per full cycle of the Johnson-Trotter structure embedded in Algorithm P, so its sign is toggled independently across visits.
Since each element $x$ experiences an independent sequence of toggles determined only by the number of times it reaches position $1$, and since the traversal of permutations guarantees that every relative configuration of “entry-to-front events” is realized consistently with the full cycle, every assignment of signs occurs exactly once across the traversal of the $n!$ underlying permutations. This yields all $2^n n!$ signed permutations.
The final step returns from the last permutation to the first via the closing interchange of Algorithm P, and the induced sign evolution also returns all $b_i$ to their initial values because each element completes an even number of front-position visits over the full cycle.
Thus the construction generates a Hamiltonian cycle on the signed permutation graph using only adjacent swaps and negation of the first element.
This completes the proof. ∎