8
\$\begingroup\$

The word "levencycle" is inspired by cyclic levenquine challenge.

Definitions

A 1-dup permutation of order \$n\$ is some permutation of \$1, \cdots, n\$ plus one duplicate number in the range.

For example, 1-dup permutations of order 3 include 1, 3, 2, 2 and 3, 2, 1, 3. There are 36 distinct 1-dup permutations of order 3, and \$\frac{(n+1)!\cdot n}{2}\$ of those of order \$n\$ in general.

A Hamiltonian levencycle combines the concept of Hamiltonian cycle (a cycle going through all vertices in a given graph) and Levenstein distance (minimal edit distance between two strings). Informally, it is a cycle going through all possible sequences by changing only one number at once.

For example, the following is a Hamiltonian levencycle of order 2: (the connection from the last to the start is implied)

(1, 1, 2) -> (1, 2, 2) -> (1, 2, 1) -> (2, 2, 1) -> (2, 1, 1) -> (2, 1, 2)

For order 3, found by automated search using Z3:

(1, 1, 2, 3) -> (1, 2, 2, 3) -> (1, 2, 1, 3) -> (1, 2, 3, 3) ->
(1, 2, 3, 2) -> (1, 3, 3, 2) -> (1, 1, 3, 2) -> (3, 1, 3, 2) ->
(3, 1, 2, 2) -> (3, 1, 2, 1) -> (3, 1, 2, 3) -> (2, 1, 2, 3) ->
(2, 1, 1, 3) -> (2, 1, 3, 3) -> (2, 1, 3, 2) -> (2, 1, 3, 1) ->
(2, 2, 3, 1) -> (1, 2, 3, 1) -> (3, 2, 3, 1) -> (3, 2, 1, 1) ->
(3, 2, 2, 1) -> (3, 3, 2, 1) -> (1, 3, 2, 1) -> (2, 3, 2, 1) ->
(2, 3, 3, 1) -> (2, 3, 1, 1) -> (2, 3, 1, 2) -> (2, 3, 1, 3) ->
(2, 2, 1, 3) -> (3, 2, 1, 3) -> (3, 2, 1, 2) -> (3, 1, 1, 2) ->
(3, 3, 1, 2) -> (1, 3, 1, 2) -> (1, 3, 2, 2) -> (1, 3, 2, 3)

Challenge

Given an integer \$n \ge 2\$, output a Hamiltonian levencycle of 1-dup permutations of order \$n\$. The output format is flexible. Assume that such a cycle exists; for values of \$n\$ where it does not exist, the behavior is undefined (you may do whatever you want).

Standard rules apply. The shortest code in bytes wins.

\$\endgroup\$
3
  • \$\begingroup\$ In both examples the final element is distance 1 from the first, so that you can return to the starting point. I assume this is required? \$\endgroup\$
    – Jonah
    Jul 13 at 3:23
  • 1
    \$\begingroup\$ @Jonah Yes, because the required output is a "cycle". (the connection from the last to the start is implied) \$\endgroup\$
    – Bubbler
    Jul 13 at 3:24
  • \$\begingroup\$ This is always possible for even n, and I suspect it's always possible for odd n too. \$\endgroup\$
    – Nitrodon
    Jul 15 at 21:03
4
\$\begingroup\$

Jelly, 110 bytes

ñ-ị$X⁸ṣU2¦jɗ
0ịị®ḟ
Œ!⁸œṖþẎṣ€Ẏ¥þ⁸Q€;@"Ẏ¥þ@";þ`ạ/Þ€;"Q¥U$ƊẎḅQ¥€⁸ṢFỤ’:‘sʋ1ịLƊƲ©ṛ1ç`X;@ṛÑ¥¹?Ɗ,®Ẉ⁻/Ɗ¿Ñç0ċ1¬Ɗ¿ƲịḢ€Ɗḃ

Try it online!

A full program that takes an integer and returns a list of lists of integers. Not written primarily to be compact but for efficiency and speed. Can solve the problem for n=5 in around 5 seconds on TIO and gets most of the way for n=6 within 60 seconds. This uses a modified version of the algorithm described in the post linked by Jonah. However, that lost only covered a Hamiltonian path and so there’s an additional bit to ensure a cycle is found. The code to find the Levenstein neighbours is also longer than minimal so that it completes in time - a more naive but shorter solution for that bit still completes within a few seconds for n=5 but rapidly becomes unworkable for bigger n.

Full explanation to follow.

\$\endgroup\$
4
\$\begingroup\$

Wolfram Language (Mathematica), 172 bytes

(DeleteDuplicates[Flatten[Table[Permutations[Join[{i},Range[#]]],{i,Range[#]}],1]]//FindHamiltonianPath[AdjacencyGraph[Table[If[1==EditDistance[i,j],1,0],{i,#},{j,#}]]]&)&;

Try it online!

This is my first Wolfram golf, and as a golf I think it's pretty terrible, but I'm posting because it calculates n=3 almost instantly, which seems to support my conjecture from the other answer that there is a more efficient (possibly probabilistic) algorithm for this. These docs suggest this as well, though don't say which of the algorithms discussed powers FindHamiltonianPath.

n=4 times out on TIO, and I haven't tested it longer than a minute, so I'm not sure how long its execution time would be.

\$\endgroup\$
1
\$\begingroup\$

J, 76 bytes

0{[:(#~([:*/2(1=1#.*@|@-/)\],{.)"2)@(i.@!@#A."2])@~.[:,/i.@!@>:A."1,"0 1~@i.

Try it online!

Brute force, not a great golf. Should work in theory but too slow to test on anything above 2.

General Hamiltonian circuit is NP, but I'm wondering if there's something special about the structure of this problem that allows a clever, much faster algorithm? I had another approach that's 2^n instead of n! but that's still not close to good enough.

Perhaps this? https://stackoverflow.com/questions/1987183/randomized-algorithm-for-finding-hamiltonian-path-in-a-directed-graph

Maybe I'll give it a shot tomorrow...

\$\endgroup\$
1
\$\begingroup\$

Jelly, 21 bytes

R;€`Œ!€ẎQŒ!ṙ1nƊ§ỊẠƲƇḢ

Try It Online!

-1 byte thanks to Nick Kennedy, then fixed for +1 thanks to Nick Kennedy

Full explanation to come if I remember.

\$\endgroup\$
3
  • \$\begingroup\$ On further reflection, this finds all paths including ones that aren’t cycles. For n=2, there’s no difference, but if your solution ever completed for n=3, it would include some invalid solutions. \$\endgroup\$ Jul 15 at 17:23
  • \$\begingroup\$ jht.hyper-neutrino.xyz/… adds one byte but should theoretically work for larger n \$\endgroup\$ Jul 15 at 17:27
  • \$\begingroup\$ @NickKennedy Ah, my bad, I didn't realize there was a difference and of course couldn't test 3 :) thank you \$\endgroup\$
    – hyper-neutrino
    Jul 15 at 17:30

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.