Say I have a quantum circuit of $w+1$ qubits with a permutation gate (mapping computational basis states to computational basis states) that does the permutation $(i, i+1)(i+4, i+5)$ on $w+1$ qubits if $i$ is odd and the permutation $(i+1, i+2)(i+3, i+4)$ if $i$ is even, for some fixed $i$ in the range $1 \leq i \leq 2^W -2$. Is it possible to decompose the $(w+1)$-qubit permutation gate into some $w$-qubit permutation gates, $\mathrm{SWAP}$s and $\mathrm{NOT}$s? How? (Ideally, I'd like to avoid using $\mathrm{SWAP}$s and $\mathrm{NOT}$s due to certain implementation issues.)
I think it should be possible because of Lemma $2$ in the appendix of the paper Generating the group of reversible logic gates (Vos, Ra & Storme, 2002) (PDF):
The subgroup of exchangers $\mathbf{E}_w$, augmented with the $\text{NOT}$ gate and the $\text{CONTROLLED}^{w−2}$ $\text{NOT}$ gate, generates the group of even simple control gates.
but I'm not sure how to construct the circuit.