Databases
StackOverflow2013
Postsdbo
PO
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    text
    copied!<p>If you just want the number of strings of a certain length, you could just multiply the compatibility matrix with itself a few times, and sum it's values.</p> <blockquote> <p><em>n</em> = <em>length of string</em><br> <em>A</em> = <em>compatibility matrix</em><br> <em>number of possible strings</em> = sum of <em>A</em><sup><em>n</em>-1</sup></p> </blockquote> <p>A few examples:</p> <pre><code>n = 1 | 1 0 0 0 0 | | 0 1 0 0 0 | | 0 0 1 0 0 | | 0 0 0 1 0 | | 0 0 0 0 1 | sum: 5 n = 3 | 2 0 0 0 0 | | 0 1 0 0 0 | | 0 0 1 1 0 | | 0 0 1 1 0 | | 0 0 0 0 1 | sum: 8 n = 8 | 0 0 8 8 0 | | 0 0 0 0 1 | | 8 0 0 0 0 | | 8 0 0 0 0 | | 0 1 0 0 0 | sum: 34 </code></pre> <p>The original matrix (row <em>i</em>, column <em>j</em>) could be thought of as the number of strings that start with symbol <em>i</em>, and whose next symbol is symbol <em>j</em>. Alternatively, you could see it as number of strings of length <strong>2</strong>, which start with symbol <em>i</em> and ends with symbol <em>j</em>.</p> <p>Matrix multiplication preserves this invariant, so after exponentiation, <em>A</em><sup><em>n</em>-1</sup> would contain the number of strings that start with symbol <em>i</em>, has length <em>n</em>, and ends in symbol <em>j</em>.</p> <p>See <a href="http://en.wikipedia.org/wiki/Exponentiation_by_squaring" rel="nofollow noreferrer">Wikipedia: Exponentiation by squaring</a> for an algorithm for faster calculation of matrix powers.</p> <p>(Thanks stefan.ciobaca)</p> <p>This specific case reduces to the formula:</p> <blockquote> <p><em>number of possible strings</em> = <em>f</em>(<i>n</i>) = 4 + &Sigma;<sub><em>k</em>=1..<em>n</em></sub> 2<sup>&lfloor;<sup><em>k</em>-1</sup>&frasl;<sub>2</sub>&rfloor;</sup> = <em>f</em>(<i>n</i>-1) + 2<sup>&lfloor;<sup><em>n</em>-1</sup>&frasl;<sub>2</sub>&rfloor;</sup></p> </blockquote> <pre><code>n f(n) ---- ---- 1 5 2 6 3 8 4 10 5 14 6 18 7 26 8 34 9 50 10 66 </code></pre>
 

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