Count balanced binary strings matching any of a set of masks - Code Golf Stack Exchange most recent 30 from codegolf.stackexchange.com 2019-08-21T01:01:04Z https://codegolf.stackexchange.com/feeds/question/50138 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://codegolf.stackexchange.com/q/50138 10 Count balanced binary strings matching any of a set of masks Masclins https://codegolf.stackexchange.com/users/40604 2015-05-13T19:05:09Z 2016-04-10T08:06:43Z <p>A <em>binary string</em> is a string which contains only characters drawn from <em>01</em>. A <em>balanced binary string</em> is a binary string which contains exactly as many <em>0</em>&#x200b;s as <em>1</em>&#x200b;s.</p> <p>You are given a positive integer <em>n</em> and an arbitrary number of masks, each of which is <em>2n</em> characters long, and contains only characters drawn from <em>012</em>. A binary string and a mask match if it is the same length and agrees on the character in every position where the mask doesn't have a <em>2</em>. E.g. the mask <em>011022</em> matches the binary strings <em>011000</em>, <em>011001</em>, <em>011010</em>, <em>011011</em>.</p> <p>Given <em>n</em> and the masks as input (separated by newlines), you must output the number of distinct balanced binary strings which match one or more of the masks.</p> <h2>Examples</h2> <p>Input</p> <pre><code>3 111222 000112 122020 122210 102120 </code></pre> <p>Reasoning</p> <ul> <li>The only balanced binary string matching <em>111222</em> is <strong>111000</strong>.</li> <li>The only balanced binary string matching <em>000112</em> is <strong>000111</strong>.</li> <li>The balanced binary strings matching <em>122020</em> are <em>111000</em> (already counted), <strong>110010</strong> and <strong>101010</strong>.</li> <li>The balanced binary strings matching <em>122210</em> are <em>110010</em> (already counted), <em>101010</em> (already counted) and <strong>100110</strong>.</li> <li>The balanced binary strings matching <em>102120</em> are <strong>101100</strong> and <em>100110</em> (already counted).</li> </ul> <p>So the output should be</p> <pre><code>6 </code></pre> <hr> <p>Input</p> <pre><code>10 22222222222222222222 </code></pre> <p>Reasoning</p> <ul> <li>There are <em>20 choose 10</em> balanced binary strings of length 20.</li> </ul> <p>Output</p> <pre><code>184756 </code></pre> <h2>Winner</h2> <p>The winner will be the one that computes the competition input the fastest, of course treating it the same way as it would any other input. (I use a determined code in order to have a clear winner and avoid cases where different inputs would give different winners. If you think of a better way to find the fastest code, tell me so).</p> <h3>Competition input</h3> <p><a href="http://pastebin.com/2Dg7gbfV">http://pastebin.com/2Dg7gbfV</a></p> https://codegolf.stackexchange.com/questions/50138/-/50195#50195 1 Answer by alexander-brett for Count balanced binary strings matching any of a set of masks alexander-brett https://codegolf.stackexchange.com/users/19039 2015-05-15T00:56:53Z 2015-05-15T00:56:53Z <h1>C</h1> <pre><code>#include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;string.h&gt; #include &lt;gsl/gsl_combination.h&gt; int main (int argc, char *argv[]) { printf ("reading\n"); char buffer; gets(buffer); char n = atoi(buffer); char *masks; masks = malloc(2 * n * sizeof(char)); char c,nrows,j,biggestzerorun,biggestonerun,currentzerorun,currentonerun = 0; while ((c = getchar()) &amp;&amp; c != EOF) { if (c == '\n') { nrows++; if (currentonerun &gt; biggestonerun) { biggestonerun = currentonerun; } if (currentzerorun &gt; biggestzerorun) { biggestzerorun = currentzerorun; } j=currentonerun=currentzerorun=0; masks[nrows] = malloc(2 * n * sizeof(char)); } else if (c == '0') { masks[nrows][j++] = 1; currentzerorun++; if (currentonerun &gt; biggestonerun) { biggestonerun = currentonerun; } currentonerun=0; } else if (c == '1') { masks[nrows][j++] = 2; currentonerun++; if (currentzerorun &gt; biggestzerorun) { biggestzerorun = currentzerorun; } currentonerun=0; } else if (c == '2') { masks[nrows][j++] = 3; currentonerun++; currentzerorun++; } } if (currentonerun &gt; biggestonerun) { biggestonerun = currentonerun; } if (currentzerorun &gt; biggestzerorun) { biggestzerorun = currentzerorun; } printf("preparing combinations\n"); int nmatches=0; gsl_combination *combination = gsl_combination_calloc(2*n, n); printf("entering loop:\n"); do { char vector[2*n]; char currentindex, previousindex; currentonerun = 0; memset(vector, 1, 2*n); // gsl_combination_fprintf (stdout, combination, "%u "); // printf(": "); for (char k=0; k&lt;n; k++) { previousindex = currentindex; currentindex = gsl_combination_get(combination, k); if (k&gt;0) { if (currentindex - previousindex == 1) { currentonerun++; if (currentonerun &gt; biggestonerun) { goto NEXT; } } else { currentonerun=0; if (currentindex - previousindex &gt; biggestzerorun) { goto NEXT; } } } vector[currentindex] = 2; } for (char k=0; k&lt;=nrows; k++) { char ismatch = 1; for (char l=0; l&lt;2*n; l++) { if (!(vector[l] &amp; masks[k][l])) { ismatch = 0; break; } } if (ismatch) { nmatches++; break; } } NEXT: 1; } while ( gsl_combination_next(combination) == GSL_SUCCESS ); printf ("RESULT: %i\n", nmatches); gsl_combination_free(combination); for (; nrows&gt;=0; nrows--) { free(masks[nrows]); } } </code></pre> <p>Good luck getting the big input to run on this - it'll probably take all night to get through approx. 60^30 permutations! Maybe an intermediate sized dataset might be a good idea?</p> https://codegolf.stackexchange.com/questions/50138/-/50196#50196 4 Answer by blutorange for Count balanced binary strings matching any of a set of masks blutorange https://codegolf.stackexchange.com/users/26465 2015-05-15T00:57:30Z 2015-05-15T21:15:01Z <h1>ruby, pretty fast, but it depends upon the input</h1> <p><em>Now speed-up by a factor of 2~2.5 by switching from strings to integers.</em></p> <p>Usage:</p> <pre><code>cat &lt;input&gt; | ruby this.script.rb </code></pre> <p>Eg.</p> <pre><code>mad_gaksha@madlab ~/tmp \$ ruby c50138.rb &lt; c50138.inp2 number of matches: 298208861472 took 0.05726237 s </code></pre> <p>The number of matches for a single mask a readily calculated by the binomial coefficient. So for example <code>122020</code> needs 3 <code>2</code>s filled, 1 <code>0</code> and 2 <code>1</code>. Thus there are <code>nCr(3,2)=nCr(3,1)=3!/(2!*1!)=3</code> different binary strings matching this mask.</p> <p>An intersection between n masks m_1, m_2, ... m_n is a mask q, such that a binary string s matches q only iff it matches all masks m_i.</p> <p>If we take two masks m_1 and m_2, its intersection is easily computed. Just set m_1[i]=m_2[i] if m_1[i]==2. The intersection between <code>122020</code> and <code>111222</code> is <code>111020</code>:</p> <pre><code>122020 (matched by 3 strings, 111000 110010 101010) 111222 (matched by 1 string, 111000) 111020 (matched by 1 string, 111000) </code></pre> <p>The two individual masks are matched by 3+1=4 strings, the interesection mask is matched by one string, thus there are 3+1-1=3 unique strings matching one or both masks.</p> <p>I'll call N(m_1,m_2,...) the number of strings matched all m_i. Applying the same logic as above, we can compute the number of unique strings matched by at least one mask, given by the <a href="http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle" rel="nofollow">inclusion exclusion principle</a> and see below as well, like this:</p> <pre><code>N(m_1) + N(m_2) + ... + N(m_n) - N(m_1,m_2) - ... - N(m_n-1,m_n) + N(m_1,m_2,m_3) + N(m_1,m_2,m_4) + ... N(m_n-2,m_n-1,m_n) - N(m_1,m_2,m_3,m_4) -+ ... </code></pre> <p>There are many, many, many combinations of taking, say 30 masks out of 200. </p> <p><strong>So this solution makes the assumption that not many high-order intersections of the input masks exist, ie. most n-tuples of n>2 masks will not have any common matches.</strong></p> <p>Use the code here, the code at ideone may be out-dated.</p> <ul> <li><a href="http://ideone.com/LQ0OHu" rel="nofollow">Test case 1</a>: number of matches: 6</li> <li><a href="http://ideone.com/NzGJX1" rel="nofollow">Test case 2</a>: number of matches: 184756</li> <li><a href="http://ideone.com/8h9nRb" rel="nofollow">Test case 3</a>: number of matches: 298208861472</li> <li><a href="http://ideone.com/gxUORt" rel="nofollow">Test case 4</a>: number of matches: 5</li> </ul> <p>I added a function <code>remove_duplicates</code> that can be used to pre-process the input and delete masks <code>m_i</code> such that all strings that match it also match another mask <code>m_j</code>.,For the current input, this actually takes longer as there are no such masks (or not many), so the function isn't applied to the data yet in the code below.</p> <p>Code:</p> <pre><code># factorial table FAC =  def gen_fac(n) n.times do |i| FAC &lt;&lt; FAC[i]*(i+1) end end # generates a mask such that it is matched by each string that matches m and n def diff_mask(m,n) (0..m.size-1).map do |i| c1 = m[i] c2 = n[i] c1^c2==1 ? break : c1&amp;c2 end end # counts the number of possible balanced strings matching the mask def count_mask(m) n = m.size/2 c0 = n-m.count(0) c1 = n-m.count(1) if c0&lt;0 || c1&lt;0 0 else FAC[c0+c1]/(FAC[c0]*FAC[c1]) end end # removes masks contained in another def remove_duplicates(m) m.each do |x| s = x.join m.delete_if do |y| r = /\A#{s.gsub(?3,?.)}\Z/ (!x.equal?(y) &amp;&amp; y =~ r) ? true : false end end end #intersection masks of cn masks from m.size masks def mask_diff_combinations(m,n=1,s=m.size,diff1=*m.size,j=-1,&amp;b) (j+1..s-1).each do |i| diff2 = diff_mask(diff1,m[i]) if diff2 mask_diff_combinations(m,n+1,s,diff2,i,&amp;b) if n&lt;s yield diff2,n end end end # counts the number of balanced strings matched by at least one mask def count_n_masks(m) sum = 0 mask_diff_combinations(m) do |mask,i| sum += i%2==1 ? count_mask(mask) : -count_mask(mask) end sum end time = Time.now # parse input d = STDIN.each_line.map do |line| line.chomp.strip.gsub('2','3') end d.delete_if(&amp;:empty?) d.shift d.map!{|x|x.chars.map(&amp;:to_i)} # generate factorial table gen_fac([d.size,d.size].max+1) # count masks puts "number of matches: #{count_n_masks(d)}" puts "took #{Time.now-time} s" </code></pre> <hr> <p>This is called the inclusion exclusion principle, but before somebody had pointed me to it I had my own proof, so here it goes. Doing something yourself feels great though.</p> <p>Let us consider the case of 2 masks, call then <code>0</code> and <code>1</code>, first. We take every balanced binary string and classify it according to which mask(s) it matches. <code>c0</code> is the number of those that match only mask <code>0</code>, <code>c1</code> the nunber of those that match only <code>1</code>, <code>c01</code> those that match mask <code>0</code> and <code>1</code>.</p> <p>Let <code>s0</code> be the number sum of the number of matches for each mask (they may overlap). Let <code>s1</code> be the sum of the number of matches for each pair (2-combination) of masks. Let <code>s_i</code> be the sum of the number of matches for each (i+1) combination of masks. The number of matches of n-masks is the number of binary strings matching all masks.</p> <p>If there are n masks, the desired output is the sum of all <code>c</code>'s, ie. <code>c = c0+...+cn+c01+c02+...+c(n-2)(n-1)+c012+...+c(n-3)(n-2)(n-1)+...+c0123...(n-2)(n-1)</code>. What the program computes is the alternating sum of all <code>s</code>'s, ie. <code>s = s_0-s_1+s_2-+...+-s_(n-1)</code>. We wish to proof that <code>s==c</code>.</p> <p>n=1 is obvious. Consider n=2. Counting all matches of mask <code>0</code> gives <code>c0+c01</code> (the number of strings matching only 0 + those matching both <code>0</code> and <code>1</code>), counting all matches of <code>1</code> gives <code>c1+c02</code>. We can illustrate this as follows:</p> <pre><code>0: c0 c01 1: c1 c10 </code></pre> <p>By definition, <code>s0 = c0 + c1 + c12</code>. <code>s1</code> is the sum number of matches of each 2-combination of <code>[0,1]</code>, ie. all uniqye <code>c_ij</code>s. Keep in mind that <code>c01=c10</code>.</p> <pre><code>s0 = c0 + c1 + 2 c01 s1 = c01 s = s0 - s1 = c0 + c1 + c01 = c </code></pre> <p>Thus <code>s=c</code> for n=2.</p> <p>Now consider n=3.</p> <pre><code>0 : c0 + c01 + c02 + c012 1 : c1 + c01 + c12 + c012 2 : c2 + c12 + c02 + c012 01 : c01 + c012 02 : c02 + c012 12 : c12 + c012 012: c012 s0 = c0 + c1 + c2 + 2 (c01+c02+c03) + 3 c012 s1 = c01 + c02 + c12 + 3 c012 s2 = c012 s0 = c__0 + 2 c__1 + 3 c__2 s1 = c__1 + 3 c__2 s2 = c__2 s = s0 - s1 + s2 = ... = c0 + c1 + c2 + c01 + c02 + c03 + c012 = c__0 + c__1 + c__2 = c </code></pre> <p>Thus <code>s=c</code> for n=3. <code>c__i</code> represents the of all <code>c</code>s with (i+1) indices, eg <code>c__1 = c01</code> for n=2 and <code>c__1 = c01 + c02 + c12</code> for n==3.</p> <p>For n=4, a pattern starts to emerge:</p> <pre><code>0: c0 + c01 + c02 + c03 + c012 + c013 + c023 + c0123 1: c1 + c01 + c12 + c13 + c102 + c103 + c123 + c0123 2: c2 + c02 + c12 + c23 + c201 + c203 + c213 + c0123 3: c3 + c03 + c13 + c23 + c301 + c302 + c312 + c0123 01: c01 + c012 + c013 + c0123 02: c02 + c012 + c023 + c0123 03: c03 + c013 + c023 + c0123 12: c11 + c012 + c123 + c0123 13: c13 + c013 + c123 + c0123 23: c23 + c023 + c123 + c0123 012: c012 + c0123 013: c013 + c0123 023: c023 + c0123 123: c123 + c0123 0123: c0123 s0 = c__0 + 2 c__1 + 3 c__2 + 4 c__3 s1 = c__1 + 3 c__2 + 6 c__3 s2 = c__2 + 4 c__3 s3 = c__3 s = s0 - s1 + s2 - s3 = c__0 + c__1 + c__2 + c__3 = c </code></pre> <p>Thus <code>s==c</code> for n=4.</p> <p>In general, we get binomial coefficients like this (↓ is i, → is j):</p> <pre><code> 0 1 2 3 4 5 6 . . . 0 1 2 3 4 5 6 7 . . . 1 1 3 6 10 15 21 . . . 2 1 4 10 20 35 . . . 3 1 5 15 35 . . . 4 1 6 21 . . . 5 1 7 . . . 6 1 . . . . . . . . . </code></pre> <p>To see this, consider that for some <code>i</code> and <code>j</code>, there are:</p> <ul> <li>x = ncr(n,i+1): combinations C for the intersection of (i+1) mask out of n</li> <li>y = ncr(n-i-1,j-i): for each combination C above, there are y different combinations for the intersection of (j+2) masks out of those containing C</li> <li>z = ncr(n,j+1): different combinations for the intersection of (j+1) masks out of n</li> </ul> <p>As that may sound confusing, here's the defintion applied to an example. For i=1, j=2, n=4, it looks like this (cf. above):</p> <pre><code>01: c01 + c012 + c013 + c0123 02: c02 + c012 + c023 + c0123 03: c03 + c013 + c023 + c0123 12: c11 + c012 + c123 + c0123 13: c13 + c013 + c123 + c0123 23: c23 + c023 + c123 + c0123 </code></pre> <p>So here x=6 (01, 02, 03, 12, 13, 23), y=2 (two c's with three indices for each combination), z=4 (c012, c013, c023, c123).</p> <p>In total, there are <code>x*y</code> coefficients <code>c</code> with (j+1) indices, and there are <code>z</code> different ones, so each occurs <code>x*y/z</code> times, which we call the coefficient <code>k_ij</code>. By simple algebra, we get <code>k_ij = ncr(n,i+1) ncr(n-i-1,j-i) / ncr(n,j+1) = ncr(j+1,i+1)</code>.</p> <p>So the index is given by <code>k_ij = nCr(j+1,i+1)</code> If you recall all the defintions, all we need to show is that the alternating sum of each column gives 1.</p> <p>The alternating sum <code>s0 - s1 + s2 - s3 +- ... +- s(n-1)</code> can thus be expressed as:</p> <pre><code>s_j = c__j * ∑［(-1)^(i+j) k_ij］ for i=0..n-1 = c__j * ∑［(-1)^(i+j) nCr(j+1,i+1)］ for i=0..n-1 = c__j * ∑［(-1)^(i+j) nCr(j+1,i)］｛i=0..n｝ - (-1)^0 nCr(j+1,0) = (-1)^j c__j s = ∑［(-1)^j s_j］ for j = 0..n-1 = ∑［(-1)^j (-1)^j c__j)］ for j=0..n-1 = ∑［c__j］ for j=0..n-1 = c </code></pre> <p>Thus <code>s=c</code> for all n=1,2,3,...</p> https://codegolf.stackexchange.com/questions/50138/-/50235#50235 2 Answer by 2012rcampion for Count balanced binary strings matching any of a set of masks 2012rcampion https://codegolf.stackexchange.com/users/39174 2015-05-15T18:43:40Z 2015-05-17T21:28:36Z <h1>C</h1> <p>If you're not on Linux, or otherwise having trouble compiling, you should probably remove the timing code (<code>clock_gettime</code>).</p> <pre class="lang-c prettyprint-override"><code>#include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;time.h&gt; long int binomial(int n, int m) { if(m &gt; n/2) { m = n - m; } int i; long int result = 1; for(i = 0; i &lt; m; i++) { result *= n - i; result /= i + 1; } return result; } typedef struct isct { char *mask; int p_len; int *p; } isct; long int mask_intersect(char *mask1, char *mask2, char *mask_dest, int n) { int zero_count = 0; int any_count = 0; int i; for(i = 0; i &lt; n; i++) { if(mask1[i] == '2') { mask_dest[i] = mask2[i]; } else if (mask2[i] == '2') { mask_dest[i] = mask1[i]; } else if (mask1[i] == mask2[i]) { mask_dest[i] = mask1[i]; } else { return 0; } if(mask_dest[i] == '2') { any_count++; } else if (mask_dest[i] == '0') { zero_count++; } } if(zero_count &gt; n/2 || any_count + zero_count &lt; n/2) { return 0; } return binomial(any_count, n/2 - zero_count); } int main() { struct timespec start, end; clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &amp;start); int n; scanf("%d", &amp;n); int nn = 2 * n; int m = 0; int m_max = 1024; char **masks = malloc(m_max * sizeof(char *)); while(1) { masks[m] = malloc(nn + 1); if (scanf("%s", masks[m]) == EOF) { break; } m++; if (m == m_max) { m_max *= 2; masks = realloc(masks, m_max * sizeof(char *)); } } int i = 1; int i_max = 1024 * 128; isct *iscts = malloc(i_max * sizeof(isct)); iscts.mask = malloc(nn); iscts.p = malloc(m * sizeof(int)); int j; for(j = 0; j &lt; nn; j++) { iscts.mask[j] = '2'; } for(j = 0; j &lt; m; j++) { iscts.p[j] = j; } iscts.p_len = m; int i_start = 0; int i_end = 1; int sign = 1; long int total = 0; int mask_bin_len = 1024 * 1024; char* mask_bin = malloc(mask_bin_len); int mask_bin_count = 0; int p_bin_len = 1024 * 128; int* p_bin = malloc(p_bin_len * sizeof(int)); int p_bin_count = 0; while (i_end &gt; i_start) { for (j = i_start; j &lt; i_end; j++) { if (i + iscts[j].p_len &gt; i_max) { i_max *= 2; iscts = realloc(iscts, i_max * sizeof(isct)); } isct *isct_orig = iscts + j; int x; int x_len = 0; int i0 = i; for (x = 0; x &lt; isct_orig-&gt;p_len; x++) { if(mask_bin_count + nn &gt; mask_bin_len) { mask_bin_len *= 2; mask_bin = malloc(mask_bin_len); mask_bin_count = 0; } iscts[i].mask = mask_bin + mask_bin_count; mask_bin_count += nn; long int count = mask_intersect(isct_orig-&gt;mask, masks[isct_orig-&gt;p[x]], iscts[i].mask, nn); if (count &gt; 0) { isct_orig-&gt;p[x_len] = isct_orig-&gt;p[x]; i++; x_len++; total += sign * count; } } for (x = 0; x &lt; x_len; x++) { int p_len = x_len - x - 1; iscts[i0 + x].p_len = p_len; if(p_bin_count + p_len &gt; p_bin_len) { p_bin_len *= 2; p_bin = malloc(p_bin_len * sizeof(int)); p_bin_count = 0; } iscts[i0 + x].p = p_bin + p_bin_count; p_bin_count += p_len; int y; for (y = 0; y &lt; p_len; y++) { iscts[i0 + x].p[y] = isct_orig-&gt;p[x + y + 1]; } } } sign *= -1; i_start = i_end; i_end = i; } printf("%lld\n", total); clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &amp;end); int seconds = end.tv_sec - start.tv_sec; long nanoseconds = end.tv_nsec - start.tv_nsec; if(nanoseconds &lt; 0) { nanoseconds += 1000000000; seconds--; } printf("%d.%09lds\n", seconds, nanoseconds); return 0; } </code></pre> <p>Example cases:</p> <pre><code>robert@unity:~/c/se-mask\$ gcc -O3 se-mask.c -lrt -o se-mask robert@unity:~/c/se-mask\$ head testcase-long 30 210211202222222211222112102111220022202222210122222212220210 010222222120210221012002220212102220002222221122222220022212 111022212212022222222220111120022120122121022212211202022010 022121221020201212200211120100202222212222122222102220020212 112200102110212002122122011102201021222222120200211222002220 121102222220221210220212202012110201021201200010222200221002 022220200201222002020110122212211202112011102220212120221111 012220222200211200020022121202212222022012201201210222200212 210211221022122020011220202222010222011101220121102101200122 robert@unity:~/c/se-mask\$ ./se-mask &lt; testcase-long 298208861472 0.001615834s robert@unity:~/c/se-mask\$ head testcase-hard 8 0222222222222222 1222222222222222 2022222222222222 2122222222222222 2202222222222222 2212222222222222 2220222222222222 2221222222222222 2222022222222222 robert@unity:~/c/se-mask\$ ./se-mask &lt; testcase-hard 12870 3.041261458s robert@unity:~/c/se-mask\$ </code></pre> <p>(Times are for an i7-4770K CPU at 4.1 GHz.) Be careful, <code>testcase-hard</code> uses around 3-4 GB of memory.</p> <p>This is pretty much an implementation of inclusion-exclusion method blutorange came up with, but done so that it will handle intersections of any depth. <s>The code as written is spending a lot of time on memory allocation, and will get even faster once I optimize the memory management.</s></p> <p>I shaved off around 25% on <code>testcase-hard</code>, but the performance on the original (<code>testcase-long</code>) is pretty much unchanged, since not much memory allocation is going on there. I'm going to tune a bit more before I call it: I think I might be able to get a 25%-50% improvement on <code>testcase-long</code> too.</p> <h1>Mathematica</h1> <p>Once I noticed this was a #SAT problem, I realized I could use Mathematica's built-in <code>SatisfiabilityCount</code>:</p> <pre><code>AbsoluteTiming[ (* download test case *) input = Map[FromDigits, Characters[ Rest[StringSplit[ Import["http://pastebin.com/raw.php?i=2Dg7gbfV", "Text"]]]], {2}]; n = Length[First[input]]; (* create boolean function *) bool = BooleanCountingFunction[{n/2}, n] @@ Array[x, n] &amp;&amp; Or @@ Table[ And @@ MapIndexed[# == 2 || Xor[# == 1, x[First[#2]]] &amp;, i], {i, input}]; (* count instances *) SatisfiabilityCount[bool, Array[x, n]] ] </code></pre> <p>Output:</p> <pre><code>{1.296944, 298208861472} </code></pre> <p>That's 298,208,861,472 masks in 1.3 seconds (i7-3517U @ 1.9 GHz), including the time spent downloading the test case from pastebin.</p>