StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>So you've got a big set of strings of length <code>N</code> bits (where <code>N</code> is approximately 100), and you want a simple logic expression that matches those strings and none others?</p> <p>You could try to make a program that builds the Kernaugh map for you. It would be an interesting exercise. I don't remember much about Kernaugh maps, but I think the labels on rows and columns arranged using a Gray code.</p> <p>Or you could just try to make the problem more tractable for hand-made Kernaugh maps. For each of the strings, find the bits that are common to all of them. Then print a list of the remaining bit positions for the human to build a map of.</p> <p>A bit of Python code:</p> <pre><code>str_len = 5 strs = [ [0,0,0,0,1], [0,0,0,0,0], [0,0,0,1,0], [0,0,0,1,1], ] for i in range(str_len): if all([x[i] for x in strs]): print 'Bit %d is 1' % i elif not any([x[i] for x in strs]): print 'Bit %d is 0' % i else: print 'Bit %d is contingent' % i </code></pre> <p>At that point you could try to think of ways to encode the <code>B</code> remaining contingent bits. In this example, it so happens that all cases are covered (and you could detect that as a special case -- e.g. <code>N = 2^B</code>).</p> <p>A brute force algorithm for finding a formula for the contingent bits would be:</p> <ol> <li>Pick the next contingent bit <code>i</code>.</li> <li>Divide S into S0 (the subset where bit <code>i</code> = 0) and S1 (the subset where bit <code>i</code> = 1).</li> <li>Recursively find the formulas f0 and f1 for S0 and S1 respectively.</li> <li>The formula for S is <code>(~b[i] & f0) | (b[i] & f1)</code>.</li> </ol> <p>There are some optimisations. The easy one is where S0 or S1 is empty -- then just omit that branch of the resulting formula. Another one is where all possible combinations are in a set (similar to the example above); the formula doesn't need to refer to the bits in that case. The hardest one is finding a good order to iterative over the bits in. Doing it naively in order may result in a less-than-optimal formula.</p> <p>You could in fact skip the first suggestion above and run this over all bits. Bits which are always 1 or 0 would simply yield trivial cases where S0 or S1 is empty.</p> <p>This rather messy Python code performs the algorithm with a few optimisations. <strong>N.B.</strong> It's not tested much and doesn't necessarily produce optimal output!</p> <pre><code>def get_formula(S, i=0): # Special case where it's an empty set -- return a tautology if len(S) == 0: return '1' remaining_bits = len(S[0]) - i # Special case where no bits are left if remaining_bits <= 0: return '1' # Partition the set S0 = filter(lambda x: x[i] == 0, S) S1 = filter(lambda x: x[i] == 1, S) f0 = get_formula(S0, i+1) f1 = get_formula(S1, i+1) # Special cases where one subset is empty # Also special case for subformula being tautology if len(S1) == 0: if f0 == '1': return '~b[%d]' % i return '~b[%d] & (%s)' % (i, f0) if len(S0) == 0: if f1 == '1': return 'b[%d]' % i return 'b[%d] & (%s)' % (i, f1) # Special cases where one or both subformulas was a tautology if f0 == '1' and f1 == '1': return '1' if f0 == '1': return '~b[%d] | b[%d] & (%s)' % (i, i, f1) if f1 == '1': return '~b[%d] & (%s) | b[%d]' % (i, f0, 1) # General case return '~b[%d] & (%s) | b[%d] & (%s)' % (i, f0, i, f1) strs = [ [0,0,0,0,1], [0,0,0,0,0], [0,0,0,1,0], [0,0,0,1,1], ] print get_formula(strs) </code></pre> <p>Finally, I think one way to make this code find more optimal formulas would be to scan ahead in <code>S</code> for bits that are always 0 or always 1, and process them early. The remaining continginent bits in each subset will get pushed into the deeply-nested subformulas where they will form less redundant formulas than when they are processed too early. I think this will in effect simulate a Kernaugh-map style construction: at each step, the set of always 0 or always 1 bits defines a rectangle on the map. Find that set, process them all at once (e.g. as a compact formula <code>~b[0] & ~b[1] & ~b[2]</code>) then recurse on the remaining bits. You need to keep track of which bit positions have already been processed, rather than doing them in order using <code>i</code>.</p> <p>(Actually, now that I think about it, for optimal formulas you also need to partition smartly by selecting a bunch of correlated bits at a time. An interesting problem...)</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