Hitung string biner seimbang yang cocok dengan salah satu set topeng

10

Sebuah String biner adalah string yang hanya berisi karakter yang diambil dari 01 . Sebuah String biner seimbang adalah string biner yang berisi persis sebanyak 0 sebagai 1 s.

Anda diberi bilangan bulat positif n dan sejumlah topeng yang berubah-ubah, masing-masing panjangnya 2n karakter, dan hanya berisi karakter yang diambil dari 012 . String biner dan topeng cocok jika panjangnya sama dan menyetujui karakter di setiap posisi di mana topeng tidak memiliki 2 . Misalnya topeng 011022 cocok dengan string biner 011000 , 011001 , 011010 , 011011 .

Diberikan n dan topeng sebagai input (dipisahkan oleh baris baru), Anda harus menampilkan jumlah string biner seimbang berbeda yang cocok dengan satu atau lebih dari topeng.

Contohnya

Memasukkan

3
111222
000112
122020
122210
102120

Pemikiran

  • Satu-satunya string biner seimbang yang cocok dengan 111222 adalah 111000 .
  • Satu-satunya string biner seimbang yang cocok dengan 000112 adalah 000111 .
  • String biner seimbang yang cocok dengan 122020 adalah 111000 (sudah dihitung), 110010 dan 101010 .
  • String biner seimbang yang cocok dengan 122210 adalah 110010 (sudah dihitung), 101010 (sudah dihitung) dan 100110 .
  • String biner seimbang cocok 102.120 adalah 101.100 dan 100.110 (sudah dihitung).

Jadi hasilnya seharusnya

6

Memasukkan

10
22222222222222222222

Pemikiran

  • Ada 20 pilih 10 string biner seimbang dengan panjang 20.

Keluaran

184756

Pemenang

Pemenang akan menjadi orang yang menghitung input kompetisi tercepat, tentu memperlakukannya dengan cara yang sama seperti input lainnya. (Saya menggunakan kode yang ditentukan untuk memiliki pemenang yang jelas dan menghindari kasus di mana input yang berbeda akan memberikan pemenang yang berbeda. Jika Anda memikirkan cara yang lebih baik untuk menemukan kode tercepat, katakan demikian).

Masukan kompetisi

http://pastebin.com/2Dg7gbfV

Masclins
sumber
2
Juga, saya pribadi lebih suka gist.github.com daripada pastebin, baik untuk kesalahan estetika dan masa depan.
orlp
3
@AlbertMasclans Saya pikir Anda harus berhak untuk mengubah input. Jika tidak, seseorang dapat melakukan hardcode output.
mbomb007
1
Akan bermanfaat jika Anda dapat memposting contoh kecil dalam pertanyaan, dengan hasil yang diharapkan, dan penjelasan. Saya mungkin lambat, tapi saya tidak mendapatkan definisi. Jadi sebagai contoh, karena n = 30, kami mencari urutan 30 0s atau 30 1s (dengan 2 menjadi wildcard) di setiap baris? Bisakah urutan itu tumpang tindih? Misalnya, jika saya menemukan urutan 32 1s, apakah itu dihitung sebagai 3 urutan, atau sebagai satu urutan? Bagaimana jika saya menemukan urutan 60 1s (seluruh baris)? Apakah itu 1 urutan, 2 urutan, atau 31 urutan?
Reto Koradi
3
Jadi, Anda meminta jumlah array unik dalam matriks ini yang memiliki jumlah 1s dan 0s yang sama, bukan?
ASCIIThenANSI
1
Bisakah kita memiliki lebih banyak data pengujian?
alexander-brett

Jawaban:

2

C

Jika Anda tidak menggunakan Linux, atau mengalami kesulitan dalam kompilasi, Anda mungkin harus menghapus kode timing ( 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;
}

Contoh kasus:

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$ 

(Kali ini untuk CPU i7-4770K pada 4,1 GHz.) Hati-hati, testcase-hardgunakan memori sekitar 3-4 GB.

Ini hampir merupakan implementasi dari metode inklusi-eksklusi blutorange, tetapi dilakukan sehingga akan menangani persimpangan dengan kedalaman apa pun. Kode seperti yang tertulis menghabiskan banyak waktu pada alokasi memori, dan akan menjadi lebih cepat setelah saya mengoptimalkan manajemen memori.

Saya mencukur sekitar 25% testcase-hard, tetapi kinerja pada yang asli ( testcase-long) cukup banyak tidak berubah, karena tidak banyak alokasi memori yang terjadi di sana. Saya akan menyetel sedikit lagi sebelum saya menyebutnya: Saya pikir saya mungkin bisa mendapatkan peningkatan 25% -50% testcase-longjuga.

Mathematica

Setelah saya perhatikan ini adalah masalah #SAT, saya menyadari saya bisa menggunakan built-in 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]]
]

Keluaran:

{1.296944, 298208861472}

Itu 298.208.861.472 topeng dalam 1,3 detik (i7-3517U @ 1.9 GHz), termasuk waktu yang dihabiskan untuk mengunduh test case dari pastebin.

2012 Arcampion
sumber
Jadi saya sudah menulis ulang ini di C ... sayangnya itu terlalu cepat bagi saya untuk menggunakan gperftools di atasnya! Saya akan menemukan beberapa test case yang lebih sulit sebelum saya posting besok.
Arcampion
testcase-harddapat diselesaikan dengan sangat cepat jika kode Anda mencari topeng yang dapat digabungkan. Jika kode Anda melakukan ini, maka hapuslah setiap baris lainnya (jadi /^2*02*$/tinggal kasing saja). Saya tidak berpikir case bisa dioptimalkan.
Arcampion
4

ruby, cukup cepat, tetapi itu tergantung pada input

Sekarang percepat dengan faktor 2 ~ 2.5 dengan beralih dari string ke integer.

Pemakaian:

cat <input> | ruby this.script.rb

Misalnya.

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

Jumlah kecocokan untuk masker tunggal mudah dihitung dengan koefisien binomial. Jadi misalnya 122020kebutuhan 3 2s diisi, 1 0dan 2 1. Jadi ada nCr(3,2)=nCr(3,1)=3!/(2!*1!)=3beberapa string biner yang cocok dengan topeng ini.

Persimpangan antara n mask m_1, m_2, ... m_n adalah mask q, sehingga string biner s cocok dengan q hanya jika jika cocok dengan semua mask m_i.

Jika kita mengambil dua topeng m_1 dan m_2, persimpangannya mudah dihitung. Cukup atur m_1 [i] = m_2 [i] jika m_1 [i] == 2. Persimpangan antara 122020dan 111222adalah 111020:

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

Dua topeng individu dicocokkan oleh 3 + 1 = 4 string, topeng intereseksi dicocokkan oleh satu string, sehingga ada 3 + 1-1 = 3 string unik yang cocok dengan satu atau kedua topeng.

Saya akan menelepon N (m_1, m_2, ...) jumlah string yang cocok dengan semua m_i. Dengan menerapkan logika yang sama seperti di atas, kita dapat menghitung jumlah string unik yang cocok dengan setidaknya satu topeng, yang diberikan oleh prinsip pengecualian inklusi dan lihat di bawah juga, seperti ini:

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

Ada banyak, banyak, banyak kombinasi pengambilan, misalnya 30 topeng dari 200.

Jadi solusi ini membuat asumsi bahwa tidak banyak persimpangan tingkat tinggi dari masker input, yaitu. kebanyakan n-tupel dari n> 2 topeng tidak akan memiliki kecocokan umum.

Gunakan kode di sini, kode di ideone mungkin kedaluwarsa.

Saya menambahkan fungsi remove_duplicatesyang dapat digunakan untuk pra-proses input dan menghapus topeng m_isehingga semua string yang cocok juga cocok dengan topeng lain m_j., Untuk input saat ini, ini sebenarnya membutuhkan waktu lebih lama karena tidak ada topeng seperti itu (atau tidak banyak) , jadi fungsinya belum diterapkan ke data dalam kode di bawah ini.

Kode:

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

Ini disebut prinsip pengecualian inklusi, tetapi sebelum seseorang menunjuk saya ke sana, saya punya bukti sendiri, jadi begini saja. Melakukan sesuatu sendiri terasa hebat.

Mari kita perhatikan kasus 2 topeng, panggil dulu 0dan 1, pertama. Kami mengambil setiap string biner seimbang dan mengklasifikasikannya sesuai dengan topeng yang cocok. c0adalah jumlah orang-orang yang cocok hanya topeng 0, c1nunber dari orang-orang yang cocok hanya 1, c01orang-orang yang cocok masker 0dan 1.

Membiarkan s0menjadi jumlah jumlah dari jumlah kecocokan untuk setiap topeng (mereka mungkin tumpang tindih). Membiarkan s1menjadi jumlah dari jumlah kecocokan untuk setiap pasangan (2-kombinasi) dari topeng. Biarkan s_imenjadi jumlah dari jumlah kecocokan untuk setiap (i +1) kombinasi topeng. Jumlah kecocokan n-mask adalah jumlah string biner yang cocok dengan semua mask.

Jika ada n mask, output yang diinginkan adalah jumlah dari semua c, yaitu. c = c0+...+cn+c01+c02+...+c(n-2)(n-1)+c012+...+c(n-3)(n-2)(n-1)+...+c0123...(n-2)(n-1). Apa yang dihitung program adalah jumlah bolak - balik dari semua s, yaitu. s = s_0-s_1+s_2-+...+-s_(n-1). Kami ingin membuktikannya s==c.

n = 1 jelas. Pertimbangkan n = 2. Menghitung semua pertandingan topeng 0memberikan c0+c01(jumlah string yang cocok hanya 0 + mereka cocok baik 0dan 1), menghitung semua pertandingan 1memberikan c1+c02. Kita dapat menggambarkan ini sebagai berikut:

0: c0 c01
1: c1 c10

Menurut definisi s0 = c0 + c1 + c12,. s1adalah jumlah jumlah kecocokan dari setiap 2 kombinasi [0,1], yaitu. semua uniqye c_ijs. Ingat itu c01=c10.

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

Jadi s=cuntuk n = 2.

Sekarang pertimbangkan 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

Jadi s=cuntuk n = 3. c__imewakili semua dari cs dengan indeks (i +1), misalnya c__1 = c01untuk n = 2 dan c__1 = c01 + c02 + c12untuk n == 3.

Untuk n = 4, sebuah pola mulai muncul:

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

Jadi s==cuntuk n = 4.

Secara umum, kita mendapatkan koefisien binomial seperti ini (↓ is i, → is 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  .  .  . 
.                       .
.                          .
.                             .

Untuk melihat ini, pertimbangkan itu untuk beberapa idan j, ada:

  • x = ncr (n, i + 1): kombinasi C untuk persimpangan dari (i + 1) topeng dari n
  • y = ncr (ni-1, ji): untuk setiap kombinasi C di atas, ada y kombinasi yang berbeda untuk persimpangan (j + 2) topeng dari yang mengandung C
  • z = ncr (n, j + 1): kombinasi berbeda untuk persimpangan (j + 1) topeng dari n

Karena itu mungkin terdengar membingungkan, inilah definisi yang diterapkan pada contoh. Untuk i = 1, j = 2, n = 4, terlihat seperti ini (lih. Di atas):

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

Jadi di sini x = 6 (01, 02, 03, 12, 13, 23), y = 2 (dua c dengan tiga indeks untuk setiap kombinasi), z = 4 (c012, c013, c023, c023, c123).

Secara total, ada x*ykoefisien cdengan indeks (j + 1), dan ada yang zberbeda, sehingga masing-masing terjadi x*y/zkali, yang kita sebut koefisien k_ij. Dengan aljabar sederhana, kita dapatkan k_ij = ncr(n,i+1) ncr(n-i-1,j-i) / ncr(n,j+1) = ncr(j+1,i+1).

Jadi indeks diberikan oleh k_ij = nCr(j+1,i+1)Jika Anda mengingat semua definisi, yang perlu kita tunjukkan adalah bahwa jumlah bolak-balik dari setiap kolom menghasilkan 1.

Dengan s0 - s1 + s2 - s3 +- ... +- s(n-1)demikian jumlah alternatif dapat dinyatakan sebagai:

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

Jadi s=cuntuk semua n = 1,2,3, ...

blutorange
sumber
1
Saya tidak yakin apakah Anda sadar, tetapi metode yang Anda terapkan adalah en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle , jadi Anda tidak perlu membuktikannya, jika ini yang ingin Anda coba melakukan. Juga sementara tidak diperlukan untuk kasus uji Anda bisa menghilangkan dari topeng kelompok yang benar-benar termasuk dalam topeng lain dalam kelompok. Misalnya dalam TC5: 0011 < 2211, 0022 < 0222. Saya pikir ini membuat kelompok tidak lebih besar dari 2*n, meskipun masih terlalu besar dalam kasus terburuk.
nutki
@nutki Saya tidak menyadari hal ini, jadi terima kasih atas tautannya. Kadang-kadang, membuktikan dan memikirkan sesuatu untuk diri sendiri masih merupakan latihan yang baik, :). Adapun saran Anda, ya, itu terjadi pada saya untuk melakukan itu, tapi saya tidak berpikir saya akan mengimplementasikannya kecuali ada test case yang ditambahkan yang mengharuskan untuk mendapatkan hasil dalam jumlah waktu yang wajar.
blutorange
@blutorange apakah Anda berpikir untuk menggunakan pohon keputusan?
Abr001am
Saya pikir maksud Anda persimpangan (cocok dengan kedua topeng), bukan penyatuan (cocok dengan satu atau topeng lainnya).
Arcampion
@ 2012 Arcampion Seperti dalam unifying two masksistilah ini unionmasuk akal bagi saya dan saya dapat mendefinisikan seperti itu, tetapi Anda benar, demi kepentingan saling pengertian yang saya raih. @ Agawa001 Bisakah Anda lebih spesifik? Juga, jika Anda punya ide bagus untuk membuatnya lebih cepat, silakan gunakan ide apa pun dari jawaban ini untuk program / jawaban Anda. Untuk saat ini, ini cukup cepat untuk test case yang besar, dan jika dibuat multi-threaded harus mengambil <0,1s, yang di bawah pengukuran / perbandingan yang berarti, sehingga untuk test case yang lebih keras diperlukan.
blutorange
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]);
    }
}

Semoga berhasil mendapatkan input besar untuk dijalankan - ini mungkin akan memakan waktu sepanjang malam untuk mendapatkan sekitar. 60 ^ 30 permutasi! Mungkin dataset berukuran menengah mungkin merupakan ide yang bagus?

alexander-brett
sumber