StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POGenerating Variants of a String According to Rules
text
Body
copied!<p><strong>What I'm hoping to get as an answer:</strong></p> <p>I'm hoping someone can tell me the general class(es) of algorithms which solve these types of problems. Ideally, the algorithms could be run in parallel, but I am still very interested in algorithms which can only be executed sequentially. Specific algorithm names or literature references would be much appreciated :)</p> <p><strong>What I've done so far:</strong></p> <p>I basically approached this using some brute force methods involving generating all permutations of a given string length and then filtering out ones that don't match the set of rules. I don't like this approach though, as it is obviously quite slow and quickly becomes limited by my computing power (1 PC) and the size of the string. I started coming up with little optimizations to this approach, but felt like I must be re-inventing the wheel and there is likely a set of algorithms out there already for solving these kinds of problems.</p> <h2>Problem description:</h2> <p>Consider a string like the following:</p> <blockquote> <p>ABCDBEACBDECDBAACBE</p> </blockquote> <p>I'm trying to figure out efficient methods for generating ALL permutations of a string which follow a set of rules/conditions.</p> <h2>Examples of Rules:</h2> <hr> <h1>Simple example:</h1> <ol> <li>There must be at least 2 differences from the original string</li> <li>The differences must be in the alphabet set (A,B,C,D,E)</li> </ol> <p>An example of a single, valid permutation, given the above rules would be:</p> <p><strong>DE</strong> CDBEACBDECDBAACBE</p> <hr> <h1>Complicated rule set example 1:</h1> <ol> <li>There must be at least 2 differences from the original string</li> <li>The differences must be in the alphabet set (A,B,C,D,E)</li> <li><strong>NEW:</strong> Differences must occur within defined index ranges of the string</li> <li><strong>NEW:</strong> Each range must 2 have differences</li> </ol> <p>So, given the original string, let's say we have the following ranges defined:</p> <blockquote> <p>[(0,4), (8,14)]</p> </blockquote> <p>This would look like:</p> <blockquote> <p>[ABCDB]EAC[BDECDBA]ACBE</p> </blockquote> <p>And a valid permutation example is:</p> <p><strong>BD</strong> CDBEACB <strong>AB</strong> CDBAACBE</p> <hr> <h1>Complicated rule set example 2:</h1> <ol> <li>There must be at least 2 differences from the original string</li> <li>The differences must be in the alphabet set (A,B,C,D,E)</li> <li>Differences must occur within defined index ranges of the string</li> <li>Each range must have 2 differences</li> <li><strong>NEW:</strong> Differences must be a specific combination, let's say "AB"</li> </ol> <p>Ranges:</p> <blockquote> <p>[(0,4), (8,14)]</p> </blockquote> <p>A valid permutation example is:</p> <p>B <strong>AB</strong> DBEACB <strong>AB</strong> CDBAACBE</p> <hr> <h1>Complicated rule set example 3:</h1> <ol> <li>There must be at least 2 differences from the original string</li> <li>The differences must be in the alphabet set (A,B,C,D,E)</li> <li>Differences must occur within defined index ranges of the string</li> <li>Each range must have 2 differences</li> <li><strong>NEW:</strong> Ranges can overlap</li> </ol> <p>Ranges:</p> <blockquote> <p>[(0,4), (3,7)]</p> </blockquote> <p>This would look like:</p> <blockquote> <p>[ABCD[B]EAC]BDECDBAACBE</p> </blockquote> <p>A valid permutation example is:</p> <p>ABC <strong>ADB</strong> ACBDECDBAACBE</p> <hr>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload