Don't ask to ask, just ask | |
PerlMonks |
Re: Detecting transpositionsby Abigail-II (Bishop) |
on Aug 06, 2003 at 13:51 UTC ( [id://281398]=note: print w/replies, xml ) | Need Help?? |
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
In Section
Seekers of Perl Wisdom
|
|