1 of 4

Stax, 23 bytes

₧¡U=δà╗▌âÜ╚g$¬g⌐☺Ñ╩⌂╪╧↕

Run and debug online!

Takes a very long time to run. A more reasonable/feasible version is

üzñ7_PZ7ƒTPNL&┘↨\:ø╧F.î*•Ç

Run and debug online!

Explanation

Uses the unpacked version to explain.

w|Nc_:=n{ch+2B}X!yx!|*{E-!f+
w                               Loop the whole program while condition is satisfied
 |N                             Next permutation (starting from the input)
   c_:=                         Index where the current array has the same index as the input (*)
       n{ch+2B}X!               Find all contiguous pairs in current string, including the pair `[last element, first element]`
                 yx!            Do the same for the input
                    |*          Outer product, contains pairs (which themselves are pairs) constructed from the last two array.
                      {   f     Only keep pairs
                       E-!      whose two elements have the same set of characters
                           +    Prepend the array at step (*).
                                This is used as the condition for the while loop