7
$\begingroup$

Informally asking, can we step through all permutations of the set $\{1,\ldots,n\}$ by just using transpositions?

More formally: For any $n\in\mathbb{N}$ let $[n] = \{1,\ldots,n\}$ and let $S_n$ be the set of all bijections (permutations) $\pi:[n]\to [n]$. For any set $X$ let $[X]^2 = \big\{\{x,y\}: x\neq y\in X\big\}$. We let $\pi,\psi\in S_n$ be connected by an edge if "they are one transposition away from each other", or more formally, set $$E_n = \big\{\{\pi,\psi\}\in [S_n]^2:\exists a<b\in[n]:\psi = (a\;\;b)\circ\pi\big\}.$$

For what $n\in\mathbb{N}$ does the graph $(S_n, E_n)$ allow for a Hamiltonian cycle? Or at least for a Hamiltonian path?

$\endgroup$
12
$\begingroup$

From V. L. Kompel'makher and V. A. Liskovets, "Sequential generation of arrangements by means of a basis of transpositions", Kibernetika 3, 17, May-June, 1975:

It is well known ([1], p. 28) that all $n!$ arrangements of $n$ symbols can be ordered without repetition so that each can be obtained from the previous one by a single transposition.

See also C. Savage, "A survey of combinatorial Gray codes", SIAM Rev., 39, 605 (1997):

Examples of combinatorial Gray codes include (1) listing all permutations of $1 \dots n$ so that consecutive permutations differ only by the swap of one pair of adjacent elements [Joh63, Tro62]

This is also addressed in Example 7.3.1 in Joyner's Adventures in Group Theory.

$\endgroup$
4
$\begingroup$

In Knuth's second fascicle of volume 4 of The Art of Computer Programming, he gives "algorithm P" (or more colloquially, the method of plain changes) for generating the permutations of a sequence with distinct elements by repeatedly interchanging adjacent pairs.

algorithm P


Earlier in the book, however, Knuth gives a cold shower on the possibility of doing something similar for multisets with repeated elements. He gives the following example, which does not have a Hamiltonian path:

Knuth's multiset example

$\endgroup$
  • 1
    $\begingroup$ Knuth is using a very restricted set of transpositions, only those of the form $(i\ j)$ with $j=i+1$; this shows that in fact one can do even better than OP is looking for in the permutation case, but it also means that there may still be a Hamiltonian path of OP's form even through multisets (for instance, $2112$ and $2211$ would be adjacent in OP's graph but not in the given one.) $\endgroup$ – Steven Stadnicki Aug 29 '17 at 18:55
  • $\begingroup$ "plain changes" must be a reference to the art of English change ringing. en.wikipedia.org/wiki/Change_ringing $\endgroup$ – Noam D. Elkies Aug 30 '17 at 0:00
  • 1
    $\begingroup$ @Noam, yes, the bell ringing at Cambridge is mentioned on that page of Knuth's fascicle, among other things. $\endgroup$ – J. M. is not a mathematician Aug 30 '17 at 0:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.