0
$\begingroup$

I am trying to essentially do what was done at this link, except for five elements instead of four.

The link gives all of the possible sequences of permutations of four elements with the following 2 constraints:

  1. Only neighbor swaps are allowed to get the next permutation in the sequence
  2. The sequence has to end on the same permutation it started on - it's a cycle

I'm trying to solve the same problem with 5 elements, find all sequences of 120 swaps that visit every permutation. There are 7 valid swaps for each row:

12345

X|||

XX|

X|X

|X||

|XX

||X|

|||X

I can only think to make a graph and find all the Hamiltonian cycles on it, and I don't know how to do that without making it take til the sun burns out. Is there a way to solve this in a reasonable amount of time?

$\endgroup$
  • $\begingroup$ Are you trying to sequence through all 120 permutations of five elements? $\endgroup$ – almagest May 11 '16 at 8:34
  • $\begingroup$ Yes. An example of the kind of valid sequence I'm looking for is produced by the steinhaus johnson trotter algorithm, where each permutation is arrived at by a series of single swaps. However, sequences with two swaps in the same row are also valid, for example swapping position 1 with position 2 and swapping position 3 with position 4 at the same time. $\endgroup$ – Sata May 11 '16 at 18:19
  • $\begingroup$ I think finding all sequences is fairly ambitious. Even counting them looks far from obvious. $\endgroup$ – almagest May 12 '16 at 4:51
  • $\begingroup$ I don't know enough about the subject to say what's possible, but I think there should be a way to do it that's computationally feasible. I just don't know enough about the subject to answer it. $\endgroup$ – Sata May 12 '16 at 14:07
  • $\begingroup$ I agree that it would be fairly easy to write a short program to count the number of ways for $n=5$, or even to print them all out. $\endgroup$ – almagest May 12 '16 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.