Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

comment on

( [id://3333]=superdoc: print w/replies, xml ) Need Help??

Okay. The strings will always be the same length (should have metioned that. Saves a test).

The strings will always be anagrams of each other, as implied but not stated.

The 'characters' of each string represent a sequence of states in the order that they are to be transitioned through.

The bigger picture is that I have a set of strings--always much less than the potential set of anagrams, but still potentially quite large--each describing an allowable sequences of transitions.

The task is to try and find a single sequence (if possible) of strings (sequences), that allows me to move through each of the sequence of states with only one pair of states (chars) changing at each step. Rather like Grey codes, but using bytes instead of chars.

That requires picking a starting sequence (string), then comparing that against each of the other strings looking for one that can be achieved with a single transposition. Then using that as the base, compare that against each of the remaining strings looking for the next 'match' and so on until the sequence of strings is complete.

If I reach a point where there is no next string, backtrack and look for a second match at the previous level, and move forward again. If all attempts to complete the sequence fail, put the original start point at the end and start again from the new start point and repeat until a sequence is found or all possiblilities have been attempted. I think that makes it an O( n * n! ) search?, hence the need for the comparison to be as fast as possible. I think Abigails original attempt will suffice for my needs and is probably the quickest, though I haven't run the bbenchmark yet. I will once I have generated some realistic sets of test data.

I think Abigail-IIs Backtracking through the regex world technique of using the regex engine to control the backtracking might be applicable here, and I was hoping for a regex solution to the comparision problem. Rather than using a code block, I thought that I might be able to use the (?(condition)Yespattern|No patterns) to decide when to backtrack or not, but I couldn't think of a regex. I can still try it with a code block, but for now it's looking more like a job for a recursive function.

Too many words, but thats the best description I can come up with for the picture in my head. I don't have any code that comes close yet, and showing the strings would be useless as the states are represented by char values < 32, which would just display as garbage. I could possibly change that to use [0-9A-Z] but skipping over the punctuation chars would be a pain.


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.


In reply to Re: Re: Detecting transpositions by BrowserUk
in thread Detecting transpositions by BrowserUk

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others perusing the Monastery: (4)
As of 2024-03-29 00:45 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found