Databases
StackOverflow2013
Postsdbo
POGenerating Variants of a String According to Rules
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POGenerating Variants of a String According to Rules
    primarykey
    data
    text
    <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>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. UStorbinsky
    1. UStorbinsky
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POGenerating Variants of a String According to Rules
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POGenerating Variants of a String According to Rules
      1. This table or related slice is empty.
      1. VTDownMod
    3. VO
      singulars
      1. POGenerating Variants of a String According to Rules
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThose don't look like [permutations](http://en.wikipedia.org/wiki/Permutation) at all. If you're asking for some library that have these things implemented, that's off topic. If you're asking for code, it would be good to show your brute force method (at least in pseudo-code). Also, just to clarify, you have 4 different sets of rules and you want code for each of them, correct? That would probably be better split into 4 different questions, or just pick the most complex one or two and try to simplify any given code to work for the simpler ones.
      singulars
      1. POGenerating Variants of a String According to Rules
      1. USDukeling
    2. COIs your alphabet always `[A, B, C, D, E]`? Are the strings always a fixed length? How many ranges do you expect and how large are those ranges? Just how complicated are the rules? Brute force is an excellent way to handle the rule set examples you've provided, because the number of permutations in those small ranges is really small. And in fact if the alphabet is always just 5 symbols, then even 10-character ranges wouldn't be unthinkable to solve with brute force. (5^10 is less than 10 million.)
      singulars
      1. POGenerating Variants of a String According to Rules
      1. USJim Mischel
    3. COI would argue that these are indeed permutations, albeit with constraints. In my combinatorics class we had similar (but simpler) questions, but were simply interested in counting rather than generating permutations. Unfortunately I don't know a general class of algorithms for this but I can say one thing. The constraints here are being stated very declaratively. I think thinking about constraints in terms of recursion (for e.g. ranges) will be better. What have you tried? Also, have you thought about posting on theoretical computer science stack exchange as well?
      singulars
      1. POGenerating Variants of a String According to Rules
      1. USJ Trana
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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