9
$\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?

Improve this question
$\endgroup$
3

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
5
$\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

Improve this answer
$\endgroup$
3
  • 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
    Commented Aug 29, 2017 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
    Commented Aug 30, 2017 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. isn't a mathematician
    Commented Aug 30, 2017 at 0:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .