0
$\begingroup$

Given some ordered list of $n$ items, I obviously have $n!$ possible arrangements. However, as a heuristic in some larger algorithm that needs to find the optimal order, I want to do some quick local exploration. One option is to walk through all possible removal & insert operations at $O(n(n-1))$. A similar option is to run through all possible 2-swaps (e.g 2-opts), also at a cost of $O(n(n-1))$. The question: do those two heuristic approaches cover the same solution set? Are they equivalent?

$\endgroup$
2
  • $\begingroup$ No, simply because $[1,2,3]$ can be transformed to $[3,1,2]$ using the first but not the second method. (Just check all possible swaps.) $\endgroup$
    – plshelp
    Sep 22 at 16:13
  • $\begingroup$ @plshelp, that sounds like a nice answer to the question! I encourage you to write it in the answer box, rather than as a comment, so we can upvote it and so the question counts as answered. We discourage answering the question in the comments. Thank you! $\endgroup$
    – D.W.
    Sep 22 at 16:14

1 Answer 1

0
$\begingroup$

No, simply because $[1,2,3]$ can be transformed to $[3,1,2]$ using one insertion but not using one swap. Just check all possible swaps to prove this.

$\endgroup$

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.