Tugas

Diberikan matriks Boolean, cari satu (atau lebih opsional) subset dari baris yang memiliki tepat satu True di setiap kolom. Anda dapat menggunakan algoritma apa pun , tetapi harus mendukung matriks yang sangat besar, seperti contoh terakhir.

Satu algoritma yang mungkin ( Knuth's Algorithm X )

Meskipun tidak ada persyaratan untuk menggunakan algoritma ini, ini mungkin merupakan pilihan terbaik Anda.

1. Jika matriks A tidak memiliki kolom, solusi parsial saat ini adalah solusi yang valid; berakhir dengan sukses.
2. Kalau tidak pilih kolom c .
3. Pilih * baris r sedemikian sehingga A _{r , c} = 1.
4. Sertakan baris r dalam solusi parsial.
5. Untuk setiap kolom j sehingga A _{r , j} = 1,
    untuk setiap baris i yang A _{i , j} = 1,
     hapus baris i dari matriks A .
    delete kolom j dari matriks A .
6. Ulangi algoritma ini secara rekursif pada berkurang matriks A .

* Langkah 3 adalah non-deterministik, dan perlu ditinjau kembali dalam kasus kegagalan untuk menemukan baris dalam permohonan selanjutnya dari langkah 3.

Memasukkan

Representasi apa pun yang diinginkan dari matriks minimal 2 × 2 A , misalnya sebagai array numerik atau Boolean

1 0 0 1 0 0 1
1 0 0 1 0 0 0
0 0 0 1 1 0 1
0 0 1 0 1 1 0
0 1 1 0 0 1 1
0 1 0 0 0 0 1

atau sebagai koleksi Universe + Set

U = {1, 2, 3, 4, 5, 6, 7}
S = {
    A = [1, 4, 7],
    B = [1, 4],
    C = [4, 5, 7],
    D = [3, 5, 6],
    E = [2, 3, 6, 7],
    F = [2, 7]
    }

atau sebagai 0 atau 1 set yang diindeks; {{1, 4, 7}, {1, 4}, {4, 5, 7}, {3, 5, 6}, {2, 3, 6, 7}, {2, 7}}.

Keluaran

Representasi yang diinginkan dari satu (atau secara opsional lebih / semua) dari solusi, misalnya sebagai array numerik atau Boolean dari baris yang dipilih

1 0 0 1 0 0 0
0 0 1 0 1 1 0
0 1 0 0 0 0 1

atau sebagai daftar Boolean yang menunjukkan baris yang dipilih {0, 1, 0, 1, 0, 1}atau sebagai daftar numerik (0 atau 1 diindeks) dari baris yang dipilih {2, 4, 6}atau sebagai daftar nama yang ditetapkan ['B', 'D', 'F'].

Lebih banyak contoh

Di:

1 0 1
0 1 1
0 1 0
1 1 1

Out: 1 3 atau 4atau 1 0 1 0atau 0 0 0 1atau [[1,3],[4]dll

Di:

1 0 1 0 1
0 1 0 1 0
1 1 0 0 1
0 1 0 1 1

Keluar: 1 1 0 0 dll

Di:

0 1 0 1 1 0 1
1 1 0 0 1 1 1
0 1 0 0 1 0 0
1 1 1 0 0 0 1
0 0 0 1 1 1 0

Keluar: 0 0 0 1 1 dll

Di:

0 1 1
1 1 0

Keluar: Tidak ada atau kesalahan atau solusi yang salah, yaitu Anda tidak harus menangani input tanpa solusi.

Di: http://pastebin.com/raw/3GAup0fr

Di luar: 0 10 18 28 32 38 48 61 62 63 68 86 90 97 103 114 120 136 148 157 162 174 177 185 186 194 209 210 218 221 228 243 252 255 263 270 271 272 273 280 291 294 295 309 310 320 323 327 339 345 350 353 355 367 372 373 375 377 382 385 386 389 397 411 417 418 431 433 441 451 457 458 459 466 473 479 488 491 498 514 517

Di: https://gist.github.com/angs/e24ac11a7d7c63d267a2279d416bc694

Di luar: 553 2162 2710 5460 7027 9534 10901 12281 12855 13590 14489 16883 19026 19592 19834 22578 25565 27230 28356 29148 29708 30818 31044 34016 34604 36806 36918 39178 43329 43562 45246 46307 47128 47906 48792 50615 51709 53911 55523 57423 59915 61293 62087 62956 64322 65094 65419 68076 70212 70845 71384 74615 76508 78688 79469 80067 81954 82255 84412 85227

Haskell, 100 93 92 87 83 80 byte

Algoritma Knuth:

g&c=filter(g.any(`elem`c))
(u:v)%a=[c:s|c<-id&u$a,s<-(not&c)v%(not&c$a)]
x%_=[x]

Hitung semua tutupan tanpa batas kedalaman-pertama dalam daftar monad. Gunakan headuntuk menghitung hanya satu karena Haskell malas. Pemakaian:

*Main> [[1],[2],[3],[4],[5],[6],[7]]%[[1, 4, 7], [1, 4], [4, 5, 7], [3, 5, 6], [2, 3, 6, 7], [2, 7]]
[[[1,4],[2,7],[3,5,6]]]

Untuk kecepatan lebih dengan menggunakan saran Knuth untuk memilih kolom dengan yang paling sedikit, gunakan ini: (115 byte, daftar datar untuk semesta). Temukan solusi pertama untuk masalah penutup pentomino besar dalam waktu kurang dari satu menit saat dikompilasi.

import Data.List
[]%_=[[]]
w%a=[c:s|c<-a,c\\(head.sortOn length.group.sort$w:a>>=id)/=c,s<-(w\\c)%[b|b<-a,c\\b==c]]

Terima kasih kepada @Zgarb untuk menghemat 1 + 3 byte!

Terima kasih kepada @ChristianSievers atas saran bijaknya dan menghemat 5 byte dan beberapa.

Tidak berkelompok (dengan alam semesta daftar datar):

knuthX [] _ = [[]]
knuthX (u:niverse) availableRows = --u chosen deterministically
  [ chosen:solution
  | let rows = filter (elem u) availableRows
  , chosen <- rows  --row chosen nondeterministically in list monad
  , solution <- knuthX
                  (filter (not.(`elem`chosen)) niverse)
                  (filter (not.any(`elem`chosen)) availableRows)
  ]

Python, 482 byte

r=lambda X,Y:u({j:set(filter(lambda i:j in Y[i],Y))for j in X},Y)
def u(X,Y,S=[]):
 if X:
  for r in list(X[min(X,key=lambda c:len(X[c]))]):
   S.append(r);C=v(X,Y,r)
   for s in u(X,Y,S):yield s
   w(X,Y,r,C);S.pop()
 else:yield list(S)
def v(X,Y,r):
 C=[]
 for j in Y[r]:
  for i in X[j]:
   for k in Y[i]:
    if k!=j:X[k].remove(i)
  C.append(X.pop(j))
 return C
def w(X,Y,r,C):
 for j in reversed(Y[r]):
  X[j]=C.pop()
  for i in X[j]:
   for k in Y[i]:
    if k!=j:X[k].add(i)

r adalah fungsi untuk memanggil dengan koleksi Universe + Set.

Golf sedikit dari halaman ini

Pemakaian:

X = {1, 2, 3, 4, 5, 6, 7}
Y = {
    'A': [1, 4, 7],
    'B': [1, 4],
    'C': [4, 5, 7],
    'D': [3, 5, 6],
    'E': [2, 3, 6, 7],
    'F': [2, 7]}

for a in r(X,Y): print a

R, 124 117 115 113 byte

Sangat tidak efisien, tetapi tidak terlalu lama dalam kode. Mencoba semua himpunan bagian yang mungkin dari baris dan memeriksa apakah semua baris berjumlah 1.

f=function(x,n=nrow(x))for(i in 1:n)for(j in 1:ncol(z<-combn(n,i)))if(all(colSums(x[k<-z[,j],,drop=F])==1))cat(k)

Mengambil matriks sebagai input. Mengembalikan rownumbers dari solusi pertama yang ditemukan. Tidak menghasilkan apa-apa jika tidak ada solusi, tetapi mungkin butuh waktu lama untuk berhenti jika inputnya besar.

Tidak Disatukan:

f=function(x, n=nrow(x)){


    for(i in 1:n){
        z=combn(n,i)

        for(j in 1:ncol(z)){
            k=x[z[,j],,drop=F]

            if(all(colSums(k)==1)){
                print(z[,j])
            }
        }
    }
}

7 byte disimpan berkat Billywob

Lain 2 byte disimpan berkat Billywob

APL (Dyalog) , 81 byte

{×≢⍉⍵:⍵∇{~1∊⍵:0⋄0≡s←⍺⍺c/⍺⌿⍨r←~∨/⍺/⍨~c←~,⍺⌿⍨f←<\⍵:⍺∇f<⍵⋄f∨r\s},⍵/⍨<\n=⌊/n←+⌿⍵⋄∧/⍵}

Cobalah online!

{ fungsi anonim:

 : jika…

  ⍵ Jika berargumen

  ⍉ ketika ditransformasikan

  ≢ memiliki jumlah baris

  × yang positif

 kemudian

  ⍵∇{... lalu terapkan fungsi ini dengan argumen kanan sebagai argumen kiri (constraint matrix), tetapi hanya setelah itu telah dimodifikasi oleh operator anonim berikut (fungsi orde tinggi):
   : jika ...
    1∊⍵ ada yang dalam argumen kanan
    ~ TIDAK
   maka ...
    0 kembalikan nol (yaitu gagal)
   ⋄ yang lain:
   : jika ...
    <\⍵ yang pertama benar dari argumen yang tepat (lit. kumulatif kurang; baris pertama)
    f← menetapkan bahwa untuk f
    ⍺⌿⍨  menggunakannya untuk menyaring baris argumen kiri
    , ravel (meratakan)
    ~ meniadakan
    c← menetapkan bahwa untuk c
    ~  meniadakan
    ⍺/⍨ menggunakannya untuk menyaring kolom argumen kiri
    ∨/ baris mana yang benar? (ATAU pengurangan)
    ~ meniadakan itu
    ⍺⌿⍨ gunakan itu untuk menyaring baris argumen kiri
    c/ gunakan c untuk menyaring kolom yang
    ⍺⍺ menerapkan fungsi luar asli (operan kiri; penutup sub-matriks)
    s← menetapkan bahwa s
    0≡  ... identik dengan nol (kegagalan), lalu (coba yang berbeda berturut-turut):
    f<⍵ benar-argumen DAN TIDAK f
    ⍺∇  recurse pada itu (melestarikan argumen kiri asli)
   ⋄ yang lain:
    r\s penggunaan nol di r untuk memasukkan nol-diisi kolom di s
    f∨  kembali f OR itu (sukses; baris f termasuk)
  }... ... pada

  +⌿⍵ jumlah argumen

  n← tetapkan itu ke n

  ⌊/ minimum itu

  n= Boolean di mana n sama dengan itu

  <\ yang pertama (kumulatif kurang dari)

  ⍵/⍨ gunakan itu untuk menyaring kolom argumen (berikan kolom pertama dengan yang paling sedikit)

  , lepaskan itu (ratakan)

 ⋄ lain

  ∧/⍵ baris yang semuanya (tidak ada, jadi ini memberikan nol untuk setiap baris)

} akhir fungsi anonim