Re: Detecting transpositions

[Abigail-II]

That sounds like O (n * n!) indeed. It looks like you are trying to find a hamiltonian path through a graph where the nodes of the graph correspond to the string in your set, and there's an edge between a pair of nodes if, and only if, the corresponding strings differ by a single transposition.

The general problem of finding an hamiltonian path is NP-complete, but for specific graphs it might be easier.

Abigail

[BrowserUk]

I'm scurrying off to look up Hamiltonin paths...in the meantime, any thoughts on my trying to use the regex engine to control the backtracking?

When you coded your N-Queens solution, was it easier or harder than a recursive subroutine? Would you do it again?

---

Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"When I'm working on a problem, I never think about beauty. I think only how to solve the problem. But when I have finished, if the solution is not beautiful, I know it is wrong." -Richard Buckminster Fuller
If I understand your problem, I can solve it! Of course, the same can be said for you.

[Abigail-II]

You want to use the regexp machine to control the backtracking when searching for a Hamiltonian path? That wouldn't be something I would do, unless to as a 'proof of concept' or so.

I'd probably go for a recursive subroutine, although there's the possibility for an iterative solution as well.

As for the N-queens problem, it basically is the recursive subroutine, except molded to fit the regexp syntax. And the only reason I did this exercise was "because I can". I don't think I would easily do such a thing in production code.

Abigail

[BrowserUk]

No production code here, so that's not a problem. I guess the idea stems from my having taken a year to understand how your N-Queens thing worked and maybe because I'd like to be able to say "because I can too":)

The reality is that the unbounded nature of the datasets involved probably means that I will need to keeps stack usage at each recursion as small as possible, which I wouldn't have control of using the RE. It was a nice thought though.

---

Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"When I'm working on a problem, I never think about beauty. I think only how to solve the problem. But when I have finished, if the solution is not beautiful, I know it is wrong." -Richard Buckminster Fuller
If I understand your problem, I can solve it! Of course, the same can be said for you.