Jumlah Matriks yang tidak tumpang tindih

Diberikan k array panjang n , hasilkan jumlah maksimum yang mungkin dengan menggunakan satu elemen dari setiap array sehingga tidak ada dua elemen dari indeks yang sama. Dijamin bahwa k <= n.

Memasukkan

Daftar nonempty array nonempty dari integer.

Keluaran

Integer yang mewakili jumlah maksimum.

Contohnya

Input -> Output
[[1]] -> 1
[[1, 3], [1, 3]] -> 4
[[1, 4, 2], [5, 6, 1]] -> 9
[[-2, -21],[18, 2]] -> 0
[[1, 2, 3], [4, 5, 6], [7, 8, 9]] -> 15
[[1, 2, 3, 4], [5, 4, 3, 2], [6, 2, 7, 1]] -> 16
[[-2, -1], [-1, -2]] -> -2

Jelly , 10 6 byte

ZŒ!ÆṭṀ

Cobalah online!

(4 byte disimpan oleh @ Dennis, yang menunjukkan bahwa Jelly memiliki built-in "jumlah main diagonal". Saya tidak mengharapkan itu memiliki salah satu dari itu; solusi sebelumnya mengimplementasikan operasi tanpa menggunakan builtin. Operasi yang dimaksud, Æṭ, didefinisikan sebagai "jejak", tetapi jejak tersebut hanya didefinisikan untuk matriks persegi; Jelly juga menerapkan generalisasi untuk matriks persegi panjang.)

Peningkatan atas jawaban lain sebagian besar dari algoritma yang lebih sederhana (sehingga terser untuk mengekspresikan); program ini awalnya ditulis dalam Brachylog v2 ( {\p\iᶠ∋₎ᵐ+}ᶠot), tetapi Jelly memiliki beberapa builtin untuk bagian-bagian dari program yang harus dijabarkan dalam Brachylog, jadi ini lebih pendek.

Penjelasan

ZŒ!ÆṭṀ
Z            Swap rows and columns
 Œ!          Find all permutations of rows (thus columns of the original)
   Æṭ        {For each permutation}, take the sum of the main diagonal
     Ṁ       Take the maximum

Seharusnya jelas bahwa untuk setiap solusi masalah, kita dapat mengubah kolom kolom dari matriks asli untuk menempatkan solusi tersebut ke diagonal utama. Jadi solusi ini hanya membalikkan itu, menemukan semua kemungkinan diagonal permutasi utama.

Perhatikan bahwa operasi "permute the kolom" dilakukan sebagai "transpose, permute the rows" tanpa repot-repot untuk mentranspos kembali; sisa dari algoritma kebetulan simetris tentang diagonal utama, jadi kita tidak perlu membatalkan transpos dan dengan demikian dapat menghemat satu byte.

J , 28 byte

>./@({.+1$:@|:\.|:@}.)@[^:]#

Cobalah online!

 >./ @  (   {.   +         1 $:@|:\. |:@}.       )       @[^:] #
(max of (1st row + recursive call on each "minor")) or count of arg if 0

Di sini panggilan rekursif dilakukan dengan $:yang mewakili fungsi anonim terbesar yang mengandungnya. Kita beruntung di J untuk memiliki primitif x u\. y, yang berlaku uuntuk "perbaikan" berturut-turut yang ydiperoleh dengan menekan infiks berturut-turut dari panjang xitem dalam y; di sini kami ingin mengesampingkan kolom berturut-turut untuk mendapatkan "anak di bawah umur", jadi kami mentransposisikan |:baris bawah (atau ekor }.) dari y, dan kemudian mengulangi pada transpos outfix mereka.

Python 3 , 94 90 89 84 80 byte

^{-4 byte terima kasih kepada xnor (menggunakan set alih-alih daftar)!}

f=lambda x,y={-1}:x>[]and max(e+f(x[1:],y|{i})for(i,e)in enumerate(x[0])if{i}-y)

Cobalah online!

Sekam , 12 11 9 byte

▲mȯΣ►L∂PT

Cobalah online!

Terima kasih kepada BMO untuk menyarankan port jawaban ais523 dan penyimpanan 2-byte, yang berhasil saya tingkatkan lebih lanjut, dan pada gilirannya BMO mengurangi 2 byte lagi.

---

Solusi sebelumnya (14 byte)

▲moΣz!¹fS=uΠmŀ

Cobalah online!

Saya tidak dapat membuat rangkaian uji karena jawaban ini menggunakan perintah argumen baris perintah pertama secara eksplisit. Tapi Husk tidak menggunakan STDIN sama sekali jadi saya memasukkan semua test case di sana, jadi Anda bisa menyalin paste di bidang argumen untuk memeriksanya. Perhatikan juga bahwa array dalam Husk mungkin tidak mengandung spasi antar elemen saat sedang diinput.

Bagaimana itu bekerja?

Rincian kode

▲moΣz!¹fS=uΠmŀ     Full program. Takes a 2D list from CLA 1 and outputs to STDOUT.
            mŀ     Length range of each list. 
           Π       Cartesian product.
       fS=u        Discard those combinations which have at least 1 non-unique element.
 mo                Map over the combinations with the following predicate:
    z!¹            Zip the 2D list input with the current combination and index accordingly.
   Σ               Sum the resulting elements.
▲                  Finally, pick the maximum.

Contoh

$$\left(\begin{matrix}1&4&2\\5&6&1\end{matrix}\right)$$

Satu harus memilih tepat satu indeks dari masing-masing sehingga tidak ada dua indeks yang sesuai. Jadi, kami menghasilkan rentang panjang baris dan hanya menyimpannya tanpa duplikat, menghasilkan kombinasi berikut (setiap kombinasi adalah kolom, bukan baris untuk menghemat ruang):

$$\left(\begin{matrix}\color{red}{1}&\color{blue}{2}&\color{green}{1}&\color{orange}{3}&2&\color{pink}{3}\\\color{red}{2}&\color{blue}{1}&\color{green}{3}&\color{orange}{1}&3&\color{pink}{2}\end{matrix}\right)$$

Kemudian, program mengindeks dalam daftar input dengan masing-masing elemen kombinasi, menghasilkan:

$$\left(\begin{matrix} \color{red}{1}&\color{blue}{4}&\color{green}{1}&\color{orange}{2}&4&\color{pink}{2}\\ \color{red}{6}&\color{blue}{5}&\color{green}{1}&\color{orange}{5}&1&\color{pink}{6} \end{matrix}\right)$$

$9$

JavaScript (ES6),  74  71 byte

Terima kasih kepada @tsh untuk mengidentifikasi 2 byte tidak berguna yang digunakan untuk memperbaiki bug.
Disimpan 3 byte berkat @tsh

f=([a,...r],k,i=1)=>a?Math.max(...a.map(n=>k&(i+=i)?-1/0:n+f(r,k|i))):0

Cobalah online!

Jelly , 13 12 byte

ẈŒpQƑƇị"€¹§Ṁ

Cobalah online!

Versi alternatif, 11 byte

ZLœ!Lị"€¹§Ṁ

Ini menggunakan œ!built-in yang baru ditambahkan , yang menghasilkan semua permutasi dengan panjang tertentu.

Cobalah online!

Bagaimana itu bekerja

ẈŒpQƑƇị"€¹§Ṁ  Main link. Argument: M (matrix)

Ẉ             Widths; compute the length of each row.
              For an n×m matrix, this yields an array m copies of n.
 Œp           Cartesian product; promote each n to [1, ..., n], then form all arrays
              that pick one k out of all m copies of [1, ..., n].
   QƑƇ        Comb by fixed unique; keep only arrays that do not change by
              deduplicating their entries.
         ¹    Identity; yield M.
      ị"€     For each of the arrays of unique elements, use its m entries to index
              into the m rows of M.
          §   Take the sums of all resulting vectors.
           Ṁ  Take the maximum.

Haskell , 65 byte

f(u:v)=maximum[e+f(take i<>drop(i+1)<$>v)|(i,e)<-zip[0..]u]
f _=0

Cobalah online!

Penjelasan & Tidak Disatukan

Fungsi take i<>drop(i+1)mengambil daftar dan menghilangkan elemen pada posisi i.

Fungsi ini fmembuat setiap elemen yang mungkin ada epada posisi i, menghilangkan elemen pada posisi idari elemen yang tersisa dan menambah eoptimal yang dihitung secara rekursif:

f(u:v)=maximum[e+f(removeElementAt i<$>v)|(i,e)<-zip[0..]u]

Dan kasus dasar untuk daftar kosong adalah 0:

f _=0

Brachylog , 18 byte

{hl⟦kp;?z₀∋₍ᵐ+}ᶠot

Cobalah online!

Penjelasan

                ot      The output is the biggest result of…
{             }ᶠ        …finding all outputs to the following predicate:
 hl⟦k                     Construct the range [0, …, n-1]
     p                    Take a permutation of that range
      ;?z₀                Zip that permutation with the Input, stopping when all elements of
                            the input are used (important because the range is possibly
                            bigger than the length of the input)
          ∋₍ᵐ             In each element of the zip, take the head'th element of the tail
             +            Sum the result

Perl 6 , 50 49 byte

{max map *.map({.[$++]}).sum,permutations [Z] $_}

Cobalah online!

Cukup pendek, meskipun ada permutationspanggilan panjang . Ini adalah blok kode anonim yang mengambil daftar daftar dan mengembalikan nomor.

Penjelasan:

{                                               } # Anonymous code block
 max                                              # Finds the maximum
                             permutations         # Of all permutations
                                          [Z] $_  # Of the transposed input
     map                                          # When mapped to
                        .sum # The sum of
         *.map({.[$++]})     # The diagonal of the matrix

K (oK) , 40, 32, 28, 19 byte

-13 byte terima kasih kepada ngn!

{|/+/(prm'x)@''!#x}

Cobalah online!

Solusi awal:

{|/+/'x./:/:(*t),'/:t:{x~?x}#+!(#x)##*x}

Cobalah online!

Catatan: Tidak berfungsi untuk test case pertama [[1]]

Penjelasan:

{ } - berfungsi dengan argumen x

                                   #     - creata a list
                               (#x)      - with length number of rows of x
                                    #*x  - of the length of the first row
                              !          - odometer (ranged permutations)
                             +           - transpose
                            #            - filter out the rows
                      {x~?x}             - that have duplicates
                    t:                   - save it to t 
                ,'/:                     - pair up each number in each row with
            (*t)                         - a number from the first row
      x./:/:                             - index x with each of the above
   +/'                                   - find the sum of each row
 |/                                      - reduce by max

Haskell , 65 byte

([]%)
p%(h:t)=maximum[x+(i:p)%t|(i,x)<-zip[0..]h,all(/=i)p]
p%_=0

Cobalah online!

---

71 byte

f m=maximum[sum b|(a,b)<-unzip<$>mapM(zip[0..])m,[x|x<-a,y<-a,x==y]==a]

Cobalah online!

The [x|x<-a,y<-a,x==y]==acek bahwa unsur-unsur ayang berbeda. Ini menggunakan sejumlah karakter yang mengejutkan, tetapi saya tidak melihat cara yang lebih pendek.

Pyth, 15 12 byte

[email protected]

Cobalah online di sini .

[email protected]   Implicit: Q=eval(input())
                Trailing Q inferred
          lhQ   Length of first element of Q
        .p      Generate all permutaions of 0 to the above
  m             Map the elements of the above, as d, using:
    @VQd          Vectorised index into Q using d
                    For i in [0-length(Q)), yield Q[i][d[i]]
   s              Take the sum of the above
 S              Sort the result of the map
e               Take the last element of the above, implicit print

Sunting: disimpan 3 byte, milik issacg

05AB1E , 18 13 byte

нgLœε‚øε`è]OZ

Saya merasa terlalu panjang, tapi saya tidak yakin bagaimana melakukan pengindeksan byte-efisien dalam 05AB1E .. Dan saya memang benar bahwa itu terlalu panjang .. -5 byte terima kasih kepada @Emigna .

Cobalah secara online atau verifikasi semua kasus uji .

Penjelasan:

н                # Take the first inner list (of the implicit input list of lists)
 g               # Pop and take its length
  L              # Create a list in the range [1, inner-length]
   œ             # Create each possible permutation of this range-list
    ε            # Map each permutation to:
     ‚           #  Pair it with the (implicit) input
      ø          #  Transpose; swap rows/columns
       ε         #  Map each to:
        `        #   Push both to the stack
         è       #   Index the permutation-nr into the inner list of the input
    ]            # Close both maps
     O           # Take the sum of each inner list
      à          # Pop and push the maximum (and output implicitly)

Contoh dijalankan:

• Memasukkan: [[1,4,2],[5,6,1]]
• Setelah langkah 1 ( нgL):[1,2,3]
• Setelah langkah 2 ( œ):[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
• Setelah langkah 3 ( ε‚):[[[[1,4,2],[5,6,1]],[1,2,3]],[[[1,4,2],[5,6,1]],[1,3,2]],[[[1,4,2],[5,6,1]],[2,1,3]],[[[1,4,2],[5,6,1]],[2,3,1]],[[[1,4,2],[5,6,1]],[3,1,2]],[[[1,4,2],[5,6,1]],[3,2,1]]]
• Setelah langkah 4 ( ø):[[[[1,4,2],1],[[5,6,1],2]],[[[1,4,2],1],[[5,6,1],3]],[[[1,4,2],2],[[5,6,1],1]],[[[1,4,2],2],[[5,6,1],3]],[[[1,4,2],3],[[5,6,1],1]],[[[1,4,2],3],[[5,6,1],2]]]
• Setelah langkah 5 ( ε`è]): [[4,1],[4,5],[2,6],[2,5],[1,6],[1,1]](CATATAN: 05AB1E diindeks 0 (dengan pembungkus otomatis), jadi pengindeksan 3menjadi [5,6,1]hasilnya 5.)
• Setelah langkah 6 ( O):[5,9,8,7,7,2]
• Output / setelah langkah 7 ( à):9

Haskell, 84 byte

import Data.List
h l=maximum[sum$snd<$>r|r<-mapM id$zip[1..]<$>l,(==)=<<nub$fst<$>r]

Cobalah online!

Ruby , 74 72 69 byte

->a{[*0...a[0].size].permutation.map{|x|a.zip(x).sum{|y,z|y[z]}}.max}

Cobalah online!

05AB1E , 7 byte

øœ€Å\Oà

Port dari Jelly CW @ ais523 menjawab , jadi pastikan Anda juga menambahkannya!

Cobalah secara online atau verifikasi semua kasus uji .

Penjelasan:

ø          # Transpose the (implicit) input; swapping row/columns
 œ         # Get all permutations
  ہ\      # Take the main diagonal of each
     O     # Sum each
      à    # Pop and push the maximum (which is output implicitly)