StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Using the example of LEN = 6, X = 3 and Y = 2...</p> <p>Build an exhaustive bit pattern generator for X bits. A simple binary counter can do this. For example, if X = 3 then a counter from 0 to 7 will generate all possible bit patterns of length 3.</p> <p>The patterns are:</p> <pre><code>000 001 010 011 100 101 110 111 </code></pre> <p>Verify the adjacency requirement as the patterns are built. Reject any patterns that do not qualify. Basically this boils down to rejecting any pattern containing fewer than 2 '1' bits (Y = 2). The list prunes down to:</p> <pre><code>011 101 110 111 </code></pre> <p>For each member of the pruned list, add a '1' bit and retest the first X bits. Keep the new pattern if it passes the adjacency test. Do the same with a '0' bit. For example this step proceeds as: </p> <pre><code>1011 <== Keep 1101 <== Keep 1110 <== Keep 1111 <== Keep 0011 <== Reject 0101 <== Reject 0110 <== Keep 0111 <== Keep </code></pre> <p>Which leaves:</p> <pre><code>1011 1101 1110 1111 0110 0111 </code></pre> <p>Now repeat this process until the pruned set is empty or the member lengths become LEN bits long. In the end the only patterns left are:</p> <pre><code>111011 111101 111110 111111 110110 110111 101101 101110 101111 011011 011101 011110 011111 </code></pre> <p>Count them up and you are done.</p> <p>Note that you only need to test the first X bits on each iteration because all the subsequent patterns were verified in prior steps.</p>

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