Visiting all strings by swapping

Question

Consider the following strings

  'dcabab',
  'cdabab',
  'dacbab',
  'adcbab',
  'cadbab',
  'acdbab',
  'dbacab',
  'bdacab',
  'dabcab',
  'adbcab',
  'badcab',
  'abdcab',
  'cbadab',
  'bcadab',
  'cabdab',
  'acbdab',
  'bacdab',
  'abcdab',
  'dabacb',
  'adbacb',
  'badacb',
  'abdacb',
  'adabcb',
  'abadcb',
  'cabadb',
  'acbadb',
  'bacadb',
  'abcadb',
  'acabdb',
  'abacdb',
  'cababd',
  'acbabd',
  'bacabd',
  'abcabd',
  'abacbd',
  'ababcd' 

If you are currently at one of those strings, you can attempt to make another one by swapping any pairs of characters. For example, you can go from 'dcabab' to 'cdabab' by swapping the first two characters. This is good because the characters that are swapped are right next to each other, that is of distance one.

The puzzle

Find a way to go from one of the strings of your choosing to all the other strings by doing one swap per new string. That is start at a string, do one swap making a new string from the list, then do another swap from the new string making another string from the list and so on. You must only ever visit strings from the list.

For those who like graphs, you can think of the strings as forming nodes in a graph and two nodes being connected by an edge if you can get from one string to another by a single swap.

Your goal is to make the distance between characters that you swap as small as possible. If you only ever need to swap adjacent characters then you have perfect solution.

If it can't be done, please explain why.

Answer 1

By introducing a dummy node that is adjacent to all other nodes, we have a traveling salesman problem on a graph with $37$ nodes and $130$ edges. The distance between nodes is $0$ if either node is the dummy and otherwise is the distance between the two swap characters. These distances are thus in $\{0,1,2,3,4\}$. The minimum total distance in a tour turns out to be:

$36$, with $2$ edges of distance $0$ (for the dummy), $34$ edges of distance $1$, and $1$ edge of distance $2$

Here is such a tour,

with the distance-$2$ edge highlighted: $$\text{DUMMY},acabdb,acbadb,acbdab,acdbab,cadbab,cdabab,dcabab,dacbab,adcbab,adbcab,abdcab,abcdab,bacdab,bcadab,cbadab,cabdab,cabadb,cababd,acbabd,abcabd,bacabd,bacadb,abcadb,abacdb,abacbd,\color{blue}{ababcd,abadcb},abdacb,badacb,badcab,bdacab,dbacab,dabcab,dabacb,adbacb,adabcb,\text{DUMMY}$$

To see that it is impossible to have a shorter tour, consider the subgraph with $37$ nodes and $89$ edges that have distances at most $1$. Removing the following $13$ nodes yields a graph with $14$ connected components: $$\text{DUMMY},abacdb,abcabd,abcdab,abdacb,acbadb,adbacb,adcbab,bacadb,badcab,cabdab,cdabab,dabcab$$ Having more connected components than removed nodes is a well-known sufficient criterion for non-Hamiltonicity.

The following $11$ nodes, the removal of which yields $12$ connected components, provide an even shorter certificate of non-Hamiltonicity: $$\text{DUMMY},abacdb,abcabd,abcdab,abdacb,acbadb,adbcab,bacadb,badcab,cabdab,dabcab$$