Policz zbalansowane ciągi binarne pasujące do dowolnego zestawu masek


10

Ciąg binarny to ciąg, który zawiera tylko znaki zaczerpnięte z 01 . Wynosi ciąg binarny jest binarny ciąg, który zawiera dokładnie jak najwięcej 0 s jako 1 s.

Otrzymujesz dodatnią liczbę całkowitą n i dowolną liczbę masek, z których każda ma długość 2n znaków i zawiera tylko znaki wyciągnięte z 012 . Łańcuch binarny i maska ​​pasują, jeśli ma taką samą długość i zgadza się na znak w każdej pozycji, w której maska ​​nie ma 2 . Np maska 011022 mecze binarne ciągi 011000 , 011001 , 011010 , 011011 .

Biorąc pod uwagę n i maski jako dane wejściowe (oddzielone znakami nowej linii), musisz wyprowadzić liczbę różnych zrównoważonych ciągów binarnych pasujących do jednej lub więcej masek.

Przykłady

Wejście

3
111222
000112
122020
122210
102120

Rozumowanie

  • Jedyny zrównoważony ciąg binarny pasujący do 111222 to 111000 .
  • Jedyny zrównoważony ciąg binarny pasujący do 000112 to 000111 .
  • Zrównoważone ciągi binarne pasujące do 122020 to 111000 (już policzone), 110010 i 101010 .
  • Zrównoważone ciągi binarne pasujące do 122210 to 110010 (już policzone), 101010 (już policzone) i 100110 .
  • Zrównoważone ciągi binarne pasujące do 102120 to 101100 i 100110 (już policzone).

Tak więc wynik powinien być

6

Wejście

10
22222222222222222222

Rozumowanie

  • Jest 20 do wyboru 10 zbalansowanych ciągów binarnych o długości 20.

Wynik

184756

Zwycięzca

Zwycięzcą zostanie ten, który najszybciej obliczy wkład konkurencji, oczywiście traktując go tak samo, jak każdy inny wkład. (Używam określonego kodu, aby mieć wyraźnego zwycięzcę i unikać przypadków, w których różne dane wejściowe dawałyby innym zwycięzcom. Jeśli zastanawiasz się, jak znaleźć najszybszy kod, powiedz mi to).

Wkład konkurencji

http://pastebin.com/2Dg7gbfV


2
Ponadto osobiście bardzo wolę gist.github.com od pastebin, zarówno ze względu na estetykę, jak i przyszłe wady.
lub

3
@AlbertMasclans Myślę, że powinieneś zastrzec sobie prawo do zmiany danych wejściowych. W przeciwnym razie ktoś może zakodować wyjście.
mbomb007

1
Byłoby użyteczne, gdybyś mógł zamieścić w pytaniu mały przykład z oczekiwanym rezultatem i wyjaśnieniem. Mogę być po prostu wolny, ale nie do końca rozumiem tę definicję. Na przykład, skoro n = 30, szukamy sekwencji 30 0 lub 30 1 (gdzie 2 to symbol wieloznaczny) w dowolnym rzędzie? Czy te sekwencje mogą się pokrywać? Na przykład, jeśli znajdę sekwencję 32 1s, czy liczy się to jako 3 sekwencje, czy jako pojedyncza sekwencja? Co się stanie, jeśli znajdę sekwencję 60 1s (cały wiersz)? Czy to 1 sekwencja, 2 sekwencje lub 31 sekwencji?
Reto Koradi

3
Pytasz więc o liczbę unikalnych tablic w tej macierzy, które mają równe liczby 1 i 0, prawda?
ASCIIThenANSI

1
Czy możemy prosić o więcej danych testowych?
Alexander-Brett

Odpowiedzi:


2

do

Jeśli nie korzystasz z systemu Linux lub masz problemy z kompilacją, prawdopodobnie powinieneś usunąć kod czasowy ( 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;
}

Przykładowe przypadki:

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$ 

(Czasy dotyczą procesora i7-4770K przy 4,1 GHz.) Bądź ostrożny, testcase-hardzużywa około 3-4 GB pamięci.

Jest to w zasadzie implementacja metody blokowania wykluczeń, która została wymyślona, ​​ale zrobiona tak, aby obsługiwała skrzyżowania o dowolnej głębokości. Napisany kod spędza dużo czasu na alokacji pamięci i będzie jeszcze szybszy, gdy zoptymalizuję zarządzanie pamięcią.

Ogoliłem około 25% testcase-hard, ale wydajność oryginalnego ( testcase-long) jest prawie niezmieniona, ponieważ tam nie dzieje się tak dużo alokacji pamięci. Zanim zadzwonię, dostroję trochę więcej: myślę, że mogę uzyskać 25% -50% poprawę testcase-long.

Matematyka

Gdy zauważyłem, że to problem #SAT, zdałem sobie sprawę, że mogę użyć wbudowanego 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]]
]

Wynik:

{1.296944, 298208861472}

To 298 208 861 472 masek w 1,3 sekundy (i7-3517U @ 1,9 GHz), w tym czas poświęcony na pobranie testowej skrzynki z pastebin.


Więc przepisałem to w C ... niestety jest dla mnie zbyt szybkie, aby użyć na nim gperftools! Zanim jutro opublikuję, znajdę trudniejsze przypadki testowe.
2012rcampion

testcase-hardmożna wykonać bardzo szybko, jeśli kod szuka masek, które można łączyć. Jeśli twój kod to robi, usuń co drugi wiersz (więc pozostały tylko /^2*02*$/przypadki). Nie sądzę, że ten przypadek można zoptymalizować.
2012rcampion

4

rubinowy, dość szybki, ale zależy to od danych wejściowych

Teraz przyspieszenie o współczynnik 2 ~ 2,5 poprzez zmianę ciągów znaków na liczby całkowite.

Stosowanie:

cat <input> | ruby this.script.rb

Na przykład.

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

Liczba dopasowań dla pojedynczej maski jest łatwo obliczana przez współczynnik dwumianowy. Na przykład 122020wymaga 3 2s wypełnienia, 1 0i 2 1. Zatem istnieją nCr(3,2)=nCr(3,1)=3!/(2!*1!)=3różne ciągi binarne pasujące do tej maski.

Przecięcie n maski m_1, m_2, ... m_n jest maską q, tak że ciąg binarny s pasuje do q tylko iff pasuje do wszystkich m_i.

Jeśli weźmiemy dwie maski m_1 i m_2, jego przecięcie można łatwo obliczyć. Wystarczy ustawić m_1 [i] = m_2 [i], jeśli m_1 [i] == 2. Przecięcie między 122020i 111222jest 111020:

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

Dwie indywidualne maski są dopasowane przez 3 + 1 = 4 ciągi, maska ​​przecięcia jest dopasowana przez jeden ciąg, więc istnieją 3 + 1-1 = 3 unikalne ciągi pasujące do jednej lub obu masek.

Wywołam N (m_1, m_2, ...) liczbę ciągów pasujących do wszystkich m_i. Stosując tę ​​samą logikę jak powyżej, możemy obliczyć liczbę unikatowych ciągów dopasowanych przez co najmniej jedną maskę, podaną przez zasadę wykluczania włączenia, i patrz również poniżej:

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

Istnieje wiele, wiele kombinacji kombinacji, powiedzmy 30 masek na 200.

To rozwiązanie zakłada więc, że nie ma wielu przecięć wyższych rzędów masek wejściowych, tj. większość n-krotek n> 2 masek nie będzie mieć wspólnych dopasowań.

Użyj kodu tutaj, kod w ideone może być przestarzały.

Dodałem funkcję, remove_duplicatesktórej można użyć do wstępnego przetworzenia danych wejściowych i usuwania masek, m_itak aby wszystkie pasujące do nich ciągi pasowały również do innej maski m_j., W przypadku bieżącego wprowadzania danych trwa to dłużej, ponieważ nie ma takich masek (lub ich niewiele) , więc funkcja nie jest jeszcze stosowana do danych w poniższym kodzie.

Kod:

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

Nazywa się to zasadą wykluczenia włączenia, ale zanim ktoś mi to wskazał, miałem swój własny dowód, więc proszę bardzo. Robienie czegoś samemu sprawia jednak przyjemność.

Rozważmy przypadek 2 masek, zadzwoń wtedy 0i 1najpierw. Bierzemy każdy zbalansowany ciąg binarny i klasyfikujemy go według pasujących masek. c0to liczba pasujących tylko do maski 0, c1liczba pasujących tylko pasujących 1, c01pasujących do maski 0i 1.

Niech s0będzie sumą liczbową liczby dopasowań dla każdej maski (mogą się nakładać). Niech s1będzie sumą liczby dopasowań dla każdej pary (2 kombinacji) masek. Niech s_ibędzie sumą liczby dopasowań dla każdej (i + 1) kombinacji masek. Liczba dopasowań n-masek to liczba ciągów binarnych pasujących do wszystkich masek.

Jeśli jest n masek, pożądanym wynikiem jest suma wszystkich c, tj. c = c0+...+cn+c01+c02+...+c(n-2)(n-1)+c012+...+c(n-3)(n-2)(n-1)+...+c0123...(n-2)(n-1). Program oblicza na przemian sumę wszystkich s, tzn. s = s_0-s_1+s_2-+...+-s_(n-1). Chcemy to udowodnić s==c.

n = 1 jest oczywiste. Zastanów się n = 2. Zliczanie wszystkich dopasowań maski 0daje c0+c01(liczba ciągów pasujących tylko do 0 + pasujących do obu 0i 1), liczenie wszystkich dopasowań 1daje c1+c02. Możemy to zilustrować w następujący sposób:

0: c0 c01
1: c1 c10

Z definicji s0 = c0 + c1 + c12. s1to łączna liczba dopasowań każdej 2 kombinacji [0,1], tj. wszystkie uniqye c_ijs. Pamiętaj o tym c01=c10.

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

Zatem s=cdla n = 2.

Teraz rozważ 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

Zatem s=cdla n = 3. c__ireprezentuje wszystkie cs ze wskaźnikami (i + 1), np. c__1 = c01dla n = 2 i c__1 = c01 + c02 + c12dla n == 3.

Dla n = 4 zaczyna się pojawiać wzór:

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

Zatem s==cdla n = 4.

Ogólnie rzecz biorąc, otrzymujemy współczynniki dwumianowe takie jak to (↓ to i, → to 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  .  .  . 
.                       .
.                          .
.                             .

Aby to zobaczyć, uważają, że dla niektórych ii jistnieją:

  • x = ncr (n, i + 1): kombinacje C dla przecięcia (i + 1) maski z n
  • y = ncr (ni-1, ji): dla każdej kombinacji C powyżej istnieją y różne kombinacje przecięcia masek (j + 2) spośród tych zawierających C
  • z = ncr (n, j + 1): różne kombinacje przecięcia masek (j + 1) z n

Może się to wydawać mylące, oto definicja zastosowana do przykładu. Dla i = 1, j = 2, n = 4 wygląda to tak (patrz wyżej):

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

Więc tutaj x = 6 (01, 02, 03, 12, 13, 23), y = 2 (dwa c z trzema indeksami dla każdej kombinacji), z = 4 (c012, c013, c023, c123).

W sumie istnieją x*ywspółczynniki co indeksach (j + 1) i są one zróżne, więc każdy zachodzi x*y/zrazy, które nazywamy współczynnikiem k_ij. Prostą algebrą otrzymujemy k_ij = ncr(n,i+1) ncr(n-i-1,j-i) / ncr(n,j+1) = ncr(j+1,i+1).

Tak więc indeks podaje: k_ij = nCr(j+1,i+1)Jeśli przypomnisz sobie wszystkie definicje, wszystko, co musimy wykazać, to że naprzemienna suma każdej kolumny daje 1.

Suma naprzemienna s0 - s1 + s2 - s3 +- ... +- s(n-1)może zatem być wyrażona jako:

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

Zatem s=cdla wszystkich n = 1,2,3 ...


1
Nie jestem pewien, czy jesteś tego świadomy, ale metodą, którą stosujesz, jest en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle , więc nie musisz tego potwierdzać, jeśli to właśnie próbujesz zrobić. Chociaż nie jest to konieczne w przypadkach testowych, możesz wyeliminować z grup maski, które są całkowicie zawarte w innej masce w grupie. Na przykład w TC5: 0011 < 2211, 0022 < 0222. Myślę, że to czyni grupy nie większymi niż 2*n, choć w najgorszym przypadku wciąż jest zbyt duża.
nutki

@nutki Nie wiedziałem o tym, więc dziękuję za link. Czasami jednak udowadnianie i samodzielne myślenie o czymś jest wciąż przyjemnym ćwiczeniem :). Co do twojej sugestii, tak, przyszło mi to do głowy, ale nie sądzę, że zamierzam ją wdrożyć, chyba że zostanie dodany przypadek testowy, który wymaga uzyskania wyniku w rozsądnym czasie.
blutorange

@blutorange czy myślałeś o użyciu drzewa decyzyjnego?
Abr001am

Myślę, że masz na myśli przecięcie (pasuje do obu masek), a nie łączenie (pasuje do jednej lub drugiej maski).
2012rcampion

@ 2012rcampion Jak dla mnie unifying two masksten termin unionma sens i ja Xan tak to określam, ale masz rację, w interesie wzajemnego zrozumienia, o którym mówiłem. @ Agawa001 Czy możesz być bardziej szczegółowy? Ponadto, jeśli masz jakiś dobry pomysł, aby przyspieszyć, skorzystaj z pomysłów z tej odpowiedzi dla swojego programu / odpowiedzi. Na razie jest wystarczająco szybki dla dużego przypadku testowego, a jeśli zostanie wykonany wielowątkowo, powinien zająć <0,1 s, co jest poniżej jakiegokolwiek znaczącego pomiaru / porównania, więc potrzebne są trudniejsze przypadki testowe.
blutorange

1

do

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

Powodzenia w uzyskaniu dużego wkładu w to - prawdopodobnie zajmie całą noc, aby przejść ok. 60 ^ 30 permutacji! Może zestaw danych o średniej wielkości może być dobrym pomysłem?

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.