Nie nakładająca się suma macierzy

Biorąc pod uwagę k tablic o długości n , wypisz maksymalną możliwą sumę, używając jednego elementu z każdej tablicy, tak aby żadne dwa elementy nie były z tego samego indeksu. Gwarantuje się, że k <= n.

Wkład

Niepusta lista niepustych tablic liczb całkowitych.

Wydajność

Liczba całkowita reprezentująca maksymalną sumę.

Przykłady

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

Galaretka , 10 6 bajtów

ZŒ!ÆṭṀ

Wypróbuj online!

(4 bajty zapisywane przez @Dennis, który wskazał, że miał „Jelly sumy głównej przekątnej” wbudowanego polecenia byłem. Nie spodziewałem się, że jeden z tych; poprzednie rozwiązanie wdrożone działania bez użycia polecenie wbudowane operacji w pytaniu. Æṭ, jest zdefiniowany jako „ślad”, ale ślad jest zdefiniowany tylko dla macierzy kwadratowych; Jelly implementuje uogólnienie również do macierzy prostokątnych.)

Poprawa w stosunku do innych odpowiedzi wynika głównie z prostszego (a więc szybszego do wyrażenia) algorytmu; program ten został pierwotnie napisany w Brachylog v2 ( {\p\iᶠ∋₎ᵐ+}ᶠot), ale Jelly ma kilka wbudowanych części programu, które muszą być napisane w Brachylog, więc wyszło to krócej.

Wyjaśnienie

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

Powinno być jasne, że dla każdego rozwiązania problemu możemy permutować kolumny oryginalnej matrycy, aby umieścić to rozwiązanie na głównej przekątnej. To rozwiązanie po prostu odwraca to, znajdując wszystkie możliwe główne przekątne permutacji.

Zauważ, że operacja „permutuj kolumny” jest wykonywana jako „transponuj, permutuj wiersze” bez zawracania sobie głowy transpozycją; reszta algorytmu jest symetryczna względem głównej przekątnej, więc nie musimy cofać transpozycji, dzięki czemu możemy zaoszczędzić bajt.

J , 28 bajtów

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

Wypróbuj online!

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

W tym przypadku odbywa się wywołanie rekurencyjne, za pomocą $:którego reprezentowana jest największa anonimowa funkcja go zawierająca. Mamy szczęście w J, że mamy prymityw x u\. y, który stosuje się udo kolejnych „przyrostków” yuzyskanych przez tłumienie kolejnych przyrostków długości xprzedmiotów y; tutaj chcemy zlikwidować kolejne kolumny, aby uzyskać „nieletnich”, więc transponujemy |:niższe rzędy (lub ogon }.) y, a następnie powtórzymy transpozycję ich outfiksów.

Python 3 , 94 90 89 84 80 bajtów

^{-4 bajty dzięki xnor (używanie zestawów zamiast list)!}

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

Wypróbuj online!

Łuska , 12 11 9 bajtów

▲mȯΣ►L∂PT

Wypróbuj online!

Dzięki BMO za zasugerowanie portu odpowiedzi ais523 i 2-bajtowego oszczędzania, które udało mi się ulepszyć, a BMO zrzuciło jeszcze 2 bajty.

Poprzednie rozwiązanie (14 bajtów)

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

Wypróbuj online!

Nie mogłem utworzyć pakietu testowego, ponieważ w tej odpowiedzi jawnie użyto pierwszego argumentu wiersza poleceń. Ale Husk w ogóle nie używa STDIN, więc zawarłem tam wszystkie przypadki testowe, więc możesz po prostu skopiować wklej w polu argumentu, aby to sprawdzić. Zauważ też, że tablice w Husk nie mogą zawierać spacji między elementami podczas wprowadzania.

Jak to działa?

Podział kodu

▲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.

Przykład

Z każdego należy wybrać dokładnie jeden indeks, aby żadne dwa wskaźniki nie były zgodne. Tak więc generujemy zakresy długości wierszy i zachowujemy tylko te bez duplikatów, uzyskując następujące kombinacje (każda kombinacja to kolumna zamiast wiersza, aby zaoszczędzić miejsce):

Następnie program indeksuje na listach wejściowych każdy element kombinacji, zwracając:

$9$

JavaScript (ES6),  74  71 bajtów

Dzięki @tsh za zidentyfikowanie 2 bezużytecznych bajtów, które zostały użyte do naprawy błędu
Zapisano 3 bajty dzięki @tsh

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

Wypróbuj online!

Galaretka , 13 12 bajtów

ẈŒpQƑƇị"€¹§Ṁ

Wypróbuj online!

Alternatywna wersja, 11 bajtów

ZLœ!Lị"€¹§Ṁ

Korzysta z nowo dodanego œ!wbudowanego, który generuje wszystkie permutacje o danej długości.

Wypróbuj online!

Jak to działa

ẈŒ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 bajtów

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

Wypróbuj online!

Wyjaśnienie i nieprzygotowany

Funkcja take i<>drop(i+1)pobiera listę i usuwa element na pozycji i.

Funkcja fpobiera każdy możliwy element ew pozycji i, usuwa elementy w pozycji iz pozostałych elementów i dodaje edo obliczonego rekurencyjnie optimum:

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

Podstawowym przypadkiem pustej listy jest po prostu 0:

f _=0

Brachylog , 18 bajtów

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

Wypróbuj online!

Wyjaśnienie

                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 bajtów

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

Wypróbuj online!

Całkiem krótko, nawet pomimo długiego permutationspołączenia. Jest to anonimowy blok kodu, który pobiera listę list i zwraca liczbę.

Wyjaśnienie:

{                                               } # 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 bajtów

-13 bajtów dzięki ngn!

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

Wypróbuj online!

Wstępne rozwiązanie:

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

Wypróbuj online!

Uwaga: nie działa dla pierwszego przypadku testowego [[1]]

Wyjaśnienie:

{ } - funkcja z argumentem 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 bajtów

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

Wypróbuj online!

71 bajtów

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

Wypróbuj online!

Do [x|x<-a,y<-a,x==y]==akontroli, że elementya są różne. To zużywa zaskakującą liczbę postaci, ale nie widziałem krótszej drogi.

Pyth, 15 12 bajtów

eSms@VQd.plh

Wypróbuj online tutaj .

eSms@VQd.plhQ   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

Edycja: zapisane 3 bajty dzięki uprzejmości issacg

05AB1E , 18 13 bajtów

нgLœε‚øε`è]OZ

Mam wrażenie, że jest zbyt długi, ale nie jestem pewien, jak efektywnie wektoryzować bajtowe indeksowanie w 05AB1E .. I rzeczywiście miałem rację, że był zbyt długi .. -5 bajtów dzięki @Emigna .

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

н                # 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)

Przykładowy przebieg:

• Wkład: [[1,4,2],[5,6,1]]
• Po kroku 1 ( нgL):[1,2,3]
• Po kroku 2 ( œ):[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
• Po kroku 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]]]
• Po kroku 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]]]
• Po kroku 5 ( ε`è]): [[4,1],[4,5],[2,6],[2,5],[1,6],[1,1]](UWAGA: 05AB1E jest indeksowany jako 0 (z automatycznym zawijaniem), więc indeksowanie 3do [5,6,1]wyników w 5.)
• Po kroku 6 ( O):[5,9,8,7,7,2]
• Wyjście / po kroku 7 ( à):9

Haskell, 84 bajty

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

Wypróbuj online!

Ruby , 74 72 69 bajtów

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

Wypróbuj online!

05AB1E , 7 bajtów

øœ€Å\Oà

Port @ ais523 na Jelly CW , więc pamiętaj też, aby ją głosować!

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

ø          # 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)