Conte cordas binárias balanceadas que correspondem a um conjunto de máscaras

10

Uma string binária é uma string que contém apenas caracteres extraídos de 01 . A cadeia binária equilibrada é uma string binário que contém exatamente como muitos 0 s como 1 s.

Você recebe um número inteiro positivo n e um número arbitrário de máscaras, cada uma com 2n caracteres e contém apenas caracteres extraídos de 012 . Uma string binária e uma máscara correspondem se tiverem o mesmo comprimento e concordarem com o caractere em todas as posições em que a máscara não tiver um 2 . Por exemplo, a máscara 011022 corresponde às cadeias binárias 011000 , 011001 , 011010 , 011011 .

Dado n e as máscaras como entrada (separadas por novas linhas), você deve gerar o número de seqüências binárias balanceadas distintas que correspondem a uma ou mais das máscaras.

Exemplos

Entrada

3
111222
000112
122020
122210
102120

Raciocínio

  • A única string binária balanceada correspondente a 111222 é 111000 .
  • A única string binária balanceada correspondente a 000112 é 000111 .
  • As cadeias binárias balanceadas correspondentes a 122020 são 111000 (já contadas), 110010 e 101010 .
  • As cadeias binárias balanceadas correspondentes a 122210 são 110010 (já contadas), 101010 (já contadas) e 100110 .
  • As cadeias binárias balanceadas correspondentes 102120 é 101100 e 100110 (já contava).

Portanto, a saída deve ser

6

Entrada

10
22222222222222222222

Raciocínio

  • Existem 20 opções para escolher 10 seqüências binárias balanceadas de comprimento 20.

Resultado

184756

Vencedora

O vencedor será aquele que calcular a entrada da competição o mais rápido, tratando-a da mesma maneira que faria com qualquer outra entrada. (Eu uso um código determinado para ter um vencedor claro e evitar casos em que entradas diferentes dariam vencedores diferentes. Se você pensar em uma maneira melhor de encontrar o código mais rápido, me diga).

Participação na competição

http://pastebin.com/2Dg7gbfV

combinatorics fastest-code balanced-string Masclins
fonte
2
Além disso, eu pessoalmente prefiro o gist.github.com ao invés do pastebin, tanto para estética quanto para futuras falhas.
orlp 13/05
3
@AlbertMasclans Acho que você deve reservar o direito de alterar a entrada. Caso contrário, alguém pode codificar a saída.
Mbomb007
11
Seria útil se você pudesse postar um pequeno exemplo na pergunta, com o resultado esperado e uma explicação. Eu posso ser lento, mas não entendo bem a definição. Então, por exemplo, como n = 30, estamos procurando sequências de 30 0s ou 30 1s (com 2 sendo um curinga) em qualquer linha? Essas sequências podem se sobrepor? Por exemplo, se eu encontrar uma sequência de 32 1s, isso conta como 3 sequências ou como uma única sequência? E se eu encontrar uma sequência de 60 1s (linha inteira)? Essa é uma sequência, duas sequências ou 31 sequências?
Reto Koradi 14/05
3
Então você está solicitando o número de matrizes exclusivas nessa matriz que têm números iguais de 1s e 0s, certo?
ASCIIThenANSI
11
Podemos ter mais alguns dados de teste, por favor?
Alexander-brett

Respostas:

2

C

Se você não estiver no Linux ou tiver problemas para compilar, provavelmente remova o código de temporização ( clock_gettime).

#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;
}

Casos de exemplo:

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$

(Os horários são para uma CPU i7-4770K a 4.1 GHz.) Cuidado, testcase-harduse cerca de 3-4 GB de memória.

Isso é basicamente uma implementação do método de inclusão-exclusão que o blutorange criou, mas feito para que ele lide com interseções de qualquer profundidade. O código escrito está gastando muito tempo na alocação de memória e ficará ainda mais rápido quando eu otimizar o gerenciamento de memória.

Eu reduzi cerca de 25% testcase-hard, mas o desempenho no original ( testcase-long) permanece praticamente inalterado, já que não há muita alocação de memória. Vou ajustar um pouco mais antes de chamá-lo: acho que também posso obter uma melhoria de 25% a 50% testcase-long.

Mathematica

Depois que percebi que era um problema do #SAT, percebi que poderia usar o built-in do Mathematica 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]]
]

Resultado:

{1.296944, 298208861472}

São 298.208.861.472 máscaras em 1,3 segundos (i7-3517U a 1,9 GHz), incluindo o tempo gasto no download do caso de teste do pastebin.

2012rcampion
fonte
Então, eu reescrevi isso em C ... infelizmente é muito rápido para eu usar o gperftools nele! Vou encontrar alguns casos de teste mais difíceis antes de publicar amanhã.
2012rcampion
testcase-hardpode ser concluído muito rapidamente se o seu código procurar máscaras que possam ser combinadas. Se o seu código fizer isso, exclua todas as outras linhas (apenas os /^2*02*$/casos permanecem). Não acho que esse caso possa ser otimizado.
2012-12-26
4

rubi, bem rápido, mas depende da entrada

Agora acelere por um fator de 2 ~ 2,5, alternando de cadeias para números inteiros.

Uso:

cat <input> | ruby this.script.rb

Por exemplo.

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

O número de correspondências para uma única máscara é prontamente calculado pelo coeficiente binomial. Por exemplo, 122020precisa de 3 2s preenchidos, 1 0e 2 1. Portanto, existem nCr(3,2)=nCr(3,1)=3!/(2!*1!)=3diferentes cadeias binárias correspondentes a essa máscara.

Uma interseção entre n máscaras m_1, m_2, ... m_n é uma máscara q, de modo que uma sequência binária s corresponda a q somente se corresponder a todas as máscaras m_i.

Se usarmos duas máscaras m_1 e m_2, sua interseção é facilmente calculada. Basta definir m_1 [i] = m_2 [i] se m_1 [i] == 2. A interseção entre 122020e 111222é 111020:

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

As duas máscaras individuais são correspondidas por 3 + 1 = 4 strings, a máscara de interseção é correspondida por uma string, portanto, existem 3 + 1-1 = 3 strings únicas que correspondem a uma ou ambas as máscaras.

Vou chamar N (m_1, m_2, ...) o número de cadeias correspondentes a todos m_i. Aplicando a mesma lógica acima, podemos calcular o número de seqüências únicas correspondidas por pelo menos uma máscara, fornecidas pelo princípio de exclusão de inclusão e ver abaixo também, assim:

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

Existem muitas, muitas, muitas combinações de tomar, digamos, 30 máscaras em 200.

Portanto, esta solução assume que não existem muitas interseções de alta ordem das máscaras de entrada, ou seja. a maioria das n-tuplas de n> 2 máscaras não terá correspondências comuns.

Use o código aqui, o código da ideone pode estar desatualizado.

Adicionei uma função remove_duplicatesque pode ser usada para pré-processar a entrada e excluir máscaras, de m_imodo que todas as seqüências correspondentes a ela também correspondam a outra máscara m_j. , portanto, a função ainda não está aplicada aos dados no código abaixo.

Código:

# 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"

Isso é chamado de princípio de exclusão de inclusão, mas antes que alguém me apontasse, eu tinha minha própria prova, então aqui está. Fazer algo você mesmo é ótimo.

Vamos considerar o caso de 2 máscaras, ligue então 0e 1, primeiro. Pegamos todas as seqüências binárias balanceadas e as classificamos de acordo com a (s) máscara (s) correspondente (s). c0é o número daqueles que correspondem apenas à máscara 0, c1o número dos que correspondem apenas 1, c01aqueles que correspondem à máscara 0e 1.

Seja s0a soma numérica do número de correspondências para cada máscara (elas podem se sobrepor). Seja s1a soma do número de correspondências para cada par (2 combinações) de máscaras. Deixeis_i a soma do número de correspondências para cada combinação (i + 1) de máscaras. O número de correspondências de n-máscaras é o número de cadeias binárias que correspondem a todas as máscaras.

Se houver n máscaras, a saída desejada é a soma de todos c, ie. c = c0+...+cn+c01+c02+...+c(n-2)(n-1)+c012+...+c(n-3)(n-2)(n-1)+...+c0123...(n-2)(n-1). O que o programa calcula é a soma alternada de todos s's, ie. s = s_0-s_1+s_2-+...+-s_(n-1). Desejamos provar isso s==c.

n = 1 é óbvio. Considere n = 2. Contando todas as correspondências de máscara 0dá c0+c01(o número de cadeias correspondendo apenas 0 + as que correspondem a ambos 0e 1), contando todas as correspondências de 1ofertas c1+c02. Podemos ilustrar isso da seguinte maneira:

0: c0 c01
1: c1 c10

Por definição s0 = c0 + c1 + c12,. s1é o número soma de correspondências de cada combinação 2 de [0,1], ie. todos uniqye c_ijs. Lembre-se disso c01=c10.

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

Assim, s=cpara n = 2.

Agora considere 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

Assim, s=cpara n = 3. c__irepresenta o de todos os cs com (i + 1) índices, por exemplo, c__1 = c01para n = 2 e c__1 = c01 + c02 + c12para n == 3.

Para n = 4, um padrão começa a emergir:

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

Assim, s==cpara n = 4.

Em geral, obtemos coeficientes binomiais como este (↓ é i, → é 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  .  .  . 
.                       .
.                          .
.                             .

Para ver isso, considere isso para alguns ie j, existem:

  • x = ncr (n, i + 1): combinações C para a interseção de (i + 1) máscara de n
  • y = ncr (ni-1, ji): para cada combinação C acima, existem y combinações diferentes para a interseção de (j + 2) máscaras daquelas que contêm C
  • z = ncr (n, j + 1): combinações diferentes para a interseção de (j + 1) máscaras de n

Como isso pode parecer confuso, aqui está a definição aplicada a um exemplo. Para i = 1, j = 2, n = 4, fica assim (cf. acima):

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

Portanto, aqui x = 6 (01, 02, 03, 12, 13, 23), y = 2 (dois c com três índices para cada combinação), z = 4 (c012, c013, c023, c123).

No total, existem x*ycoeficientes ccom índices (j + 1), e existem zdiferentes, portanto, cada um ocorre x*y/zvezes, que chamamos de coeficiente k_ij. Por álgebra simples, obtemos k_ij = ncr(n,i+1) ncr(n-i-1,j-i) / ncr(n,j+1) = ncr(j+1,i+1).

Portanto, o índice é dado por k_ij = nCr(j+1,i+1)Se você se lembrar de todas as definições, tudo o que precisamos mostrar é que a soma alternada de cada coluna fornece 1.

A soma alternada s0 - s1 + s2 - s3 +- ... +- s(n-1)pode assim ser expressa como:

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

Assim, s=cpara todos n = 1,2,3, ...

blutorange
fonte
11
Não sei se você está ciente, mas o método que você está aplicando é en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle , então você não precisa provar isso, se é isso que você está tentando Faz. Além disso, embora não seja necessário para os casos de teste, você pode eliminar das máscaras do grupo que estão completamente incluídas em outra máscara do grupo. Por exemplo, no TC5: 0011 < 2211, 0022 < 0222. Eu acho que isso faz com que os grupos não sejam maiores do que 2*n, embora ainda seja muito grande no pior dos casos.
Nutki15 /
@nutki Eu não tinha conhecimento disso, então obrigado pelo link. Ocasionalmente, provar e pensar em algo para si mesmo ainda é um bom exercício :). Quanto à sua sugestão, sim, ocorreu-me fazer isso, mas acho que não vou implementá-la, a menos que seja adicionado um caso de teste que exija que ele obtenha o resultado em um período de tempo razoável.
Blotange
@blutorange você pensou em usar a árvore de decisão?
Abr001am 15/05
Eu acho que você quer dizer interseção (corresponde às duas máscaras), não união (corresponde a uma ou a outra máscara).
2012-12-13
@ 2012rcampion Como no unifying two maskstermo, unionfaz sentido para mim e eu posso definir dessa maneira, mas você está certo, no interesse da compreensão mútua que eu chavei. @ Agawa001 Você pode ser mais específico? Além disso, se você tiver uma boa idéia para tornar isso mais rápido, sinta-se à vontade para usar as idéias desta resposta em seu programa / resposta. Por enquanto, é rápido o suficiente para o caso de teste grande e, se for multiencadeado, deve demorar <0,1s, o que está abaixo de qualquer medição / comparação significativa, portanto, para casos de teste mais difíceis são necessários.
Blotange
1

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]);
    }
}

Boa sorte para que a grande entrada seja executada - provavelmente levará a noite toda para passar aprox. 60 ^ 30 permutações! Talvez um conjunto de dados de tamanho intermediário possa ser uma boa ideia?

alexander-brett
fonte