Eine binäre Zeichenfolge ist eine Zeichenfolge, die nur Zeichen enthält, die aus 01 stammen . Eine ausgeglichene Binärzeichenfolge ist eine Binärzeichenfolge, die genau so viele 0 s wie 1 s enthält.

Sie erhalten eine positive Ganzzahl n und eine beliebige Anzahl von Masken, von denen jede 2n Zeichen lang ist und nur Zeichen enthält, die aus 012 stammen . Eine binäre Zeichenfolge und eine Maske stimmen überein, wenn sie dieselbe Länge haben und an jeder Stelle, an der die Maske keine 2 hat, mit dem Zeichen übereinstimmen . ZB die Maske 011.022 Matches die Binärketten 011000 , 011001 , 011010 , 011011 .

Wenn Sie n und die Masken als Eingabe angeben (durch Zeilenumbrüche getrennt), müssen Sie die Anzahl der unterschiedlichen ausgeglichenen Binärzeichenfolgen ausgeben, die mit einer oder mehreren der Masken übereinstimmen.

Beispiele

Eingang

3
111222
000112
122020
122210
102120

Argumentation

• Die einzige ausgeglichene binäre Zeichenfolge, die mit 111222 übereinstimmt, ist 111000 .
• Die einzige ausgeglichene binäre Zeichenfolge, die mit 000112 übereinstimmt, ist 000111 .
• Die ausgeglichenen binären Zeichenfolgen, die mit 122020 übereinstimmen, sind 111000 (bereits gezählt), 110010 und 101010 .
• Die ausgeglichenen binären Zeichenfolgen, die mit 122210 übereinstimmen, sind 110010 (bereits gezählt), 101010 (bereits gezählt) und 100110 .
• Die ausgeglichenen binären Zeichenfolgen, die mit 102120 übereinstimmen, sind 101100 und 100110 (bereits gezählt).

So sollte die Ausgabe sein

6

Eingang

10
22222222222222222222

Argumentation

• Es gibt 20 wähle 10 ausgeglichene Binärzeichenfolgen der Länge 20.

Ausgabe

184756

Gewinner

Der Gewinner ist derjenige, der den Wettbewerbseingang am schnellsten berechnet und ihn natürlich genauso behandelt wie jeden anderen Input. (Ich verwende einen bestimmten Code, um einen eindeutigen Gewinner zu haben und Fälle zu vermeiden, in denen unterschiedliche Eingaben unterschiedliche Gewinner ergeben würden. Wenn Sie einen besseren Weg finden, um den schnellsten Code zu finden, sagen Sie es mir.)

Wettbewerbsbeitrag

http://pastebin.com/2Dg7gbfV

C.

Wenn Sie nicht unter Linux arbeiten oder anderweitig Probleme beim Kompilieren haben, sollten Sie wahrscheinlich den Timing-Code ( clock_gettime) entfernen .

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

long int binomial(int n, int m) {
  if(m > n/2) {
    m = n - m;
  }
  int i;
  long int result = 1;
  for(i = 0; i < 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 < 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 > n/2 || any_count + zero_count < n/2) {
    return 0;
  }
  return binomial(any_count, n/2 - zero_count);
}

int main() {

  struct timespec start, end;
  clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);

  int n;
  scanf("%d", &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[0].mask = malloc(nn);
  iscts[0].p = malloc(m * sizeof(int));

  int j;
  for(j = 0; j < nn; j++) {
    iscts[0].mask[j] = '2';
  }
  for(j = 0; j < m; j++) {
    iscts[0].p[j] = j;
  }
  iscts[0].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 > i_start) {
    for (j = i_start; j < i_end; j++) {
      if (i + iscts[j].p_len > 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 < isct_orig->p_len; x++) {
        if(mask_bin_count + nn > 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->mask, masks[isct_orig->p[x]], iscts[i].mask, nn);
        if (count > 0) {
          isct_orig->p[x_len] = isct_orig->p[x];
          i++;
          x_len++;
          total += sign * count;
        }
      }
      for (x = 0; x < x_len; x++) {
        int p_len = x_len - x - 1;
        iscts[i0 + x].p_len = p_len;
        if(p_bin_count + p_len > 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 < p_len; y++) {
          iscts[i0 + x].p[y] = isct_orig->p[x + y + 1];
        }
      }
    }

    sign *= -1;
    i_start = i_end;
    i_end = i;

  }

  printf("%lld\n", total);

  clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);

  int seconds = end.tv_sec - start.tv_sec;
  long nanoseconds = end.tv_nsec - start.tv_nsec;
  if(nanoseconds < 0) {
    nanoseconds += 1000000000;
    seconds--;
  }

  printf("%d.%09lds\n", seconds, nanoseconds);
  return 0;
}

Beispielfälle:

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 < 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 < testcase-hard
12870
3.041261458s
robert@unity:~/c/se-mask$ 

(Die Zeiten gelten für eine i7-4770K-CPU mit 4,1 GHz.) Seien Sie vorsichtig und testcase-hardverwenden Sie etwa 3-4 GB Speicher.

Dies ist so ziemlich eine Implementierung der Einschluss-Ausschluss-Methode, die blutorange entwickelt hat, aber so, dass sie Schnittpunkte beliebiger Tiefe handhabt. Der geschriebene Code verbringt viel Zeit mit der Speicherzuweisung und wird noch schneller, sobald ich die Speicherverwaltung optimiere.

Ich habe mich bei ungefähr 25% rasiert testcase-hard, aber die Leistung des Originals ( testcase-long) ist ziemlich unverändert, da dort nicht viel Speicher zugewiesen wird. Ich werde noch ein bisschen mehr tunen, bevor ich es nenne: Ich denke, ich könnte auch eine Verbesserung von 25% bis 50% erzielen testcase-long.

Mathematica

Als ich bemerkte, dass dies ein # Sat-Problem war, wurde mir klar, dass ich das integrierte Mathematica verwenden konnte SatisfiabilityCount:

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] && 
   Or @@ Table[
     And @@ MapIndexed[# == 2 || Xor[# == 1, x[First[#2]]] &, i], {i, 
      input}];
 (* count instances *)
 SatisfiabilityCount[bool, Array[x, n]]
]

Ausgabe:

{1.296944, 298208861472}

Das sind 298.208.861.472 Masken in 1,3 Sekunden (i7-3517U bei 1,9 GHz), einschließlich der Zeit, die für das Herunterladen des Testfalls vom Pastebin aufgewendet wurde.

rubinrot, ziemlich schnell, aber es kommt auf die Eingabe an

Beschleunigen Sie jetzt um den Faktor 2 bis 2,5, indem Sie von Zeichenfolgen zu Ganzzahlen wechseln.

Verwendungszweck:

cat <input> | ruby this.script.rb

Z.B.

mad_gaksha@madlab ~/tmp $ ruby c50138.rb < c50138.inp2
number of matches: 298208861472
took 0.05726237 s

Die Anzahl der Übereinstimmungen für eine einzelne Maske wird leicht durch den Binomialkoeffizienten berechnet. So 122020braucht zum Beispiel 3 2s gefüllt, 1 0und 2 1. Daher gibt es nCr(3,2)=nCr(3,1)=3!/(2!*1!)=3verschiedene binäre Zeichenfolgen, die zu dieser Maske passen.

Ein Schnittpunkt zwischen n Masken m_1, m_2, ... m_n ist eine Maske q, so dass eine Binärzeichenfolge s nur dann mit q übereinstimmt, wenn sie mit allen Masken m_i übereinstimmt.

Wenn wir zwei Masken m_1 und m_2 nehmen, kann der Schnittpunkt leicht berechnet werden. Setzen Sie einfach m_1 [i] = m_2 [i], wenn m_1 [i] == 2. Der Schnittpunkt zwischen 122020und 111222ist 111020:

122020 (matched by 3 strings, 111000 110010 101010)
111222 (matched by 1 string, 111000)
111020 (matched by 1 string, 111000)

Die zwei einzelnen Masken werden durch 3 + 1 = 4 Zeichenfolgen abgeglichen, die Schnittmaske wird durch eine Zeichenfolge abgeglichen, daher gibt es 3 + 1-1 = 3 eindeutige Zeichenfolgen, die mit einer oder beiden Masken übereinstimmen.

Ich werde N (m_1, m_2, ...) nennen, die Anzahl der Zeichenfolgen, die mit allen m_i übereinstimmen. Unter Anwendung der gleichen Logik wie oben können wir die Anzahl der eindeutigen Zeichenfolgen berechnen, die mit mindestens einer Maske übereinstimmen, die durch das Einschlussausschlussprinzip gegeben ist, und siehe auch unten wie folgt:

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) -+ ...

Es gibt viele, viele, viele Kombinationen von etwa 30 von 200 Masken.

Diese Lösung geht also davon aus, dass nicht viele Schnittpunkte höherer Ordnung der Eingabemasken existieren, d. H. Die meisten n-Tupel mit n> 2 Masken haben keine gemeinsamen Übereinstimmungen.

Verwenden Sie den Code hier, der Code bei ideone ist möglicherweise veraltet.

• Testfall 1 : Anzahl der Übereinstimmungen: 6
• Testfall 2 : Anzahl der Übereinstimmungen: 184756
• Testfall 3 : Anzahl der Übereinstimmungen: 298208861472
• Testfall 4 : Anzahl der Übereinstimmungen: 5

Ich habe eine Funktion hinzugefügt remove_duplicates, mit der die Eingabe vorverarbeitet und Masken gelöscht werden können m_i, sodass alle übereinstimmenden Zeichenfolgen auch mit einer anderen Maske übereinstimmen m_j. Für die aktuelle Eingabe dauert dies tatsächlich länger, da es keine solchen Masken gibt (oder nicht viele). Daher wird die Funktion im folgenden Code noch nicht auf die Daten angewendet.

Code:

# factorial table
FAC = [1]
def gen_fac(n)
  n.times do |i|
    FAC << 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&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<0 || c1<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) && 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=[3]*m[0].size,j=-1,&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,&b) if n<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(&:empty?)
d.shift
d.map!{|x|x.chars.map(&:to_i)}

# generate factorial table
gen_fac([d.size,d[0].size].max+1)

# count masks
puts "number of matches: #{count_n_masks(d)}"
puts "took #{Time.now-time} s"

Dies wird als Einschluss-Ausschluss-Prinzip bezeichnet, aber bevor mich jemand darauf hingewiesen hatte, hatte ich meinen eigenen Beweis. Etwas selbst zu tun fühlt sich aber großartig an.

Betrachten wir den Fall von 2 Masken, rufen Sie dann 0und 1zuerst an. Wir nehmen jede ausgeglichene Binärzeichenfolge und klassifizieren sie nach den übereinstimmenden Masken. c0diejenigen , die Anzahl der , die nur Maske entsprechen 0, c1die nunber von denen , die nur entsprechen 1, c01diejenigen , die Spiel - Maske 0und 1.

Sei s0die Zahlensumme der Anzahl der Übereinstimmungen für jede Maske (sie können sich überlappen). Sei s1die Summe der Übereinstimmungen für jedes Maskenpaar (2-Kombinationen). Sei s_idie Summe der Anzahl der Übereinstimmungen für jede (i + 1) Maskenkombination. Die Anzahl der Übereinstimmungen von n-Masken ist die Anzahl der Binärzeichenfolgen, die allen Masken entsprechen.

Wenn es n Masken gibt, ist die gewünschte Ausgabe die Summe aller c, dh. c = c0+...+cn+c01+c02+...+c(n-2)(n-1)+c012+...+c(n-3)(n-2)(n-1)+...+c0123...(n-2)(n-1). Was das Programm berechnet, ist die alternierende Summe aller s, dh. s = s_0-s_1+s_2-+...+-s_(n-1). Das möchten wir beweisen s==c.

n = 1 ist offensichtlich. Betrachte n = 2. Das Zählen aller Übereinstimmungen von Masken 0gibt c0+c01(die Anzahl der Zeichenfolgen, die nur mit 0 übereinstimmen + die mit beiden übereinstimmen 0und 1), das Zählen aller Übereinstimmungen von 1gibt c1+c02. Wir können dies wie folgt veranschaulichen:

0: c0 c01
1: c1 c10

Per Definition s0 = c0 + c1 + c12. s1ist die Summe der Übereinstimmungen jeder 2-Kombination von [0,1], dh. alle uniqye c_ijs. Denken Sie daran c01=c10.

s0 = c0 + c1 + 2 c01
s1 = c01
s = s0 - s1 = c0 + c1 + c01 = c

Also s=cfür n = 2.

Betrachten Sie nun n = 3.

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

Also s=cfür n = 3. c__irepräsentiert das aller cs mit (i + 1) Indizes, zB c__1 = c01für n = 2 und c__1 = c01 + c02 + c12für n == 3.

Für n = 4 beginnt ein Muster aufzutauchen:

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

Also s==cfür n = 4.

Im Allgemeinen erhalten wir Binomialkoeffizienten wie diese (↓ ist i, → ist j):

   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  .  .  . 
.                       .
.                          .
.                             .

Um dies zu sehen, bedenken Sie, dass es für einige iund folgende jgibt:

• x = ncr (n, i + 1): Kombinationen C für den Schnittpunkt der (i + 1) Maske aus n
• y = ncr (ni-1, ji): Für jede Kombination C oben gibt es y verschiedene Kombinationen für den Schnittpunkt von (j + 2) Masken aus denen, die C enthalten
• z = ncr (n, j + 1): verschiedene Kombinationen für den Schnittpunkt von (j + 1) Masken aus n

Da dies verwirrend klingen mag, ist hier die Definition eines Beispiels. Für i = 1, j = 2, n = 4 sieht es so aus (vgl. Oben):

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

Hier ist also x = 6 (01, 02, 03, 12, 13, 23), y = 2 (zwei c mit drei Indizes für jede Kombination), z = 4 (c012, c013, c023, c123).

Insgesamt gibt es x*yKoeffizienten cmit (j + 1) -Indizes, und es gibt zverschiedene, so dass jedes x*y/zMal auftritt , was wir den Koeffizienten nennen k_ij. Durch einfache Algebra erhalten wirk_ij = ncr(n,i+1) ncr(n-i-1,j-i) / ncr(n,j+1) = ncr(j+1,i+1) .

Der Index ist also gegeben durch k_ij = nCr(j+1,i+1)Wenn Sie sich an alle Definitionen erinnern, müssen wir nur zeigen, dass die alternierende Summe jeder Spalte 1 ergibt.

Die alternierende Summe s0 - s1 + s2 - s3 +- ... +- s(n-1)kann somit ausgedrückt werden als:

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

Also s=cfür alle n = 1,2,3, ...

C.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <gsl/gsl_combination.h>

int main (int argc, char *argv[]) {

    printf ("reading\n");
    char buffer[100];
    gets(buffer);
    char n = atoi(buffer);

    char *masks[1000];
    masks[0] = malloc(2 * n * sizeof(char));
    char c,nrows,j,biggestzerorun,biggestonerun,currentzerorun,currentonerun = 0;

    while ((c = getchar()) && c != EOF) {
        if (c == '\n') {
            nrows++;
            if (currentonerun > biggestonerun) {
                biggestonerun = currentonerun;
            }
            if (currentzerorun > 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 > biggestonerun) {
                biggestonerun = currentonerun;
            }
            currentonerun=0;
        } else if (c == '1') {
            masks[nrows][j++] = 2;
            currentonerun++;
            if (currentzerorun > biggestzerorun) {
                biggestzerorun = currentzerorun;
            }
            currentonerun=0;
        } else if (c == '2') {
            masks[nrows][j++] = 3;
            currentonerun++;
            currentzerorun++;
        }
    }
    if (currentonerun > biggestonerun) {
        biggestonerun = currentonerun;
    }
    if (currentzerorun > 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<n; k++) {
            previousindex = currentindex;
            currentindex = gsl_combination_get(combination, k);
            if (k>0) {
                if (currentindex - previousindex == 1) {
                    currentonerun++;
                    if (currentonerun > biggestonerun) {
                        goto NEXT;
                    }
                } else {
                    currentonerun=0;
                    if (currentindex - previousindex > biggestzerorun) {
                        goto NEXT;
                    }
                }
            }
            vector[currentindex] = 2;
        }

        for (char k=0; k<=nrows; k++) {
            char ismatch = 1;
            for (char l=0; l<2*n; l++) {
                if (!(vector[l] & 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>=0; nrows--) {
        free(masks[nrows]);
    }
}

Viel Glück, dass der große Input dazu kommt - es wird wahrscheinlich die ganze Nacht dauern, bis ca. 60 ^ 30 Permutationen! Vielleicht ist ein Datensatz mittlerer Größe eine gute Idee?