# Draw this planar graph

The playing board for this puzzle is a short list of digits; there is one rule governing possible moves: The 1 may swap with a digit one place to the right; the 2 may swap with a digit two places to the right, and so on.

For example, in the list 1,3,7,2,6,5,4, you can swap 3 and 6, because the latter is 3 places to the right of 3:

┌─┐
┷ ▼
1,3,7,2,6,5,4     →     3,1,7,2,6,5,4


The only other legal moves from this position are to swap 1 and 3 (yielding 3,1,7,2,6,5,4) or to swap 2 and 5 (yielding 1,6,7,5,3,2,4):

  ┌─────┐
┷     ▼
1,3,7,2,6,5,4     →     1,6,7,2,3,5,4

┌───┐
┷   ▼
1,3,7,2,6,5,4     →     1,3,7,5,6,2,4


Here is a graph of all possible states reachable from 1,2,3:

123 → 213 → 312 → 321
↓     ↑
231 → 132


(For lists of few digits, let's just omit the separating commas).

For the 24 states reachable from 1,2,3,4, the corresponding graph can be drawn. Do so, and make sure to avoid crossing lines!

Bonus points for symmetries, aesthetics, and for using ASCII-art (or Unicode text ─ │ ┌ ┐ └ ┘).

If you need to omit the arrowheads, or the labels that distinguish the nodes, that's okay as long as the nodes are recognizable. Maybe mark the 1234 and 4321 nodes.

Is there a cycle (some sequence of two or more moves, after which the board state is the same in the beginning) for any permutation of the numbers 1,2,...,n, any n?

• I think your second example should be 1372654 -> 1375624? Commented May 21, 2020 at 18:57
• 🛈 I have no proof that this graph is cycle-free, so I've asked on math.SE.—Someone is pondering a codegolf question based on this. Commented May 26, 2020 at 2:22

The fact that flipping all sequences flips all the arrows makes for some very nice graph symmetries:

Anyone with way too much time on their hands is free to play with the length-5 version here.

• I'd be surprised if the length-5 version could be drawn without crossing lines, though! Commented May 25, 2020 at 0:12
• Of course, but maybe it has lower crossing number than it appears... Commented May 25, 2020 at 6:16

ASCII art rendering of completed graph:

 .------------------------------------.
|                                    |
|    .---------->4321<-----------.   |
|    |                           |   |
|    |                           |   |
|  4312<--4132<--1432<--1234   2341  |
|    ^      ^             |      ^   |
|    |      |             v      |   |
'->4213-->4231          2134-->2314  |
^                    |      |   |
|                    v      v   |
.->4123<----------------3124<--1324  |
|    ^                    |          |
|    |                    v          |
|  1423<--3421<--3412<--3214---------'
|    ^      ^      ^      |
|    |      |      |      v
|  2413-->2431     |    3241-->1243--.
|    ^             |      |      |   |
|    |             |      |      v   |
'--2143<---------3142<----'    1342  |
^             |             |   |
|             '-------------'   |
|                               |
'-------------------------------'

• Beautiful layout! One survey respondent says: "yes please for vertical | stems on up/down arrow heads." It would make their directions quicker to see. By the way, . periods and  ' apostrophes can work well at corners (where \\ /slashes are at present). ASCII-affectionately
– humn
Commented May 21, 2020 at 23:41

I think this works, without crossing lines:

I’d imagine the answer to the second question is

No. Consider a string of length n, with elements i=1,...,n and positions j=1,...,n. Once element n is moved away from position n, it can never return to its initial position. This is because moving from position j, j != n, to position n requires an element of at most n-1. So we conclude that element i=n must stay in place in order for this sequence to work. This is then equivalent to creating a cycle from a string of length n-1, with elements i=1,...,n-1 and positions j=1,...,n-1. We see that, by similar logic to the above, element i=n-1 must also stay in place (moving from position j, j != n-1, to position n-1 requires an element of at most n-2). By induction it follows that the starting position can not be arrived at after any moves have been made.

• You are missing 2341 Commented May 21, 2020 at 22:49
• Shoot, it was in my original diagram and forgot to transcribe — thanks Commented May 21, 2020 at 23:22

Hint:

Explore paths from 3124 to 4213 first.

Here's my own answer using unicode line-drawing characters (without arrowheads) - different lines for swaps depending on their offset:

      ┌─────────────────────────────────────────2341
2314═══1324                                  ║
│      │                                    ║
2134═══3124───────────────────────┐          ║
│      ┃   ┏━━━━━━━━━━━━3241───3214━━┓      ║
│      ┃   ┃              ║      ║   ┃   ▃▃▃║▃▃
│      ┃  1243═══1342───3142───3412  ┃   ▉4321▉
│      ┃   │┏━━━━━━━━━━━━━┛     ┃│   ┃   ▀▀▀│▀▀
▃▃│▃▃▃   ┃   │┃     ┏━━━━━━━━━━━━━┛│   ┃      │
▉1234▉   ┃  2143───2413───2431═══3421  ┃      │
▀▀║▀▀▀   ┃   ║      ║              ┃   ┃      │
║      ┗━━4123───1423━━━━━━━━━━━━┛   ┃      │
║          └───────────────────────4213═══4312
║                                    │      │
║                                  4231═══4132
1432 ────────────────────────────────────────┘

Unicode within <pre>` within a spoiler was a puzzle of its own. Kudos to Daniel!

• Wait, why does 3412 connect to 4213 directly? Doesn’t it need to connect 3412 > 3214 > 4213? Commented May 22, 2020 at 0:06
• El-Guest, you're right! Corrected. Commented May 22, 2020 at 0:12
• Thank you! Also, why does 3412 not connect to 2413? Commented May 22, 2020 at 0:17