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
  • 3
    $\begingroup$ I think maybe this has been answered here: mathoverflow.net/questions/91734/… $\endgroup$ Commented Aug 29, 2017 at 13:02
  • 4
    $\begingroup$ Relevant $\endgroup$ Commented Aug 29, 2017 at 13:21
  • 2
    $\begingroup$ It is up to you of course but I would add the reference-request tag: this kind of thing looks of such huge demand in various practical problems that it must be either widely known or impossible. $\endgroup$ Commented Aug 29, 2017 at 19:28

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$
6
$\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$ 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$ 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$ Commented Aug 30, 2017 at 0:12

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.