Soma da matriz não sobreposta

Dadas k matrizes de comprimento n , produza a soma máxima possível usando um elemento de cada matriz, de modo que não haja dois elementos do mesmo índice. É garantido que k <= n.

Entrada

Uma lista não vazia de matrizes não vazias de números inteiros.

Saída

Um número inteiro que representa a soma máxima.

Exemplos

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

Geléia , 10 6 bytes

ZŒ!ÆṭṀ

Experimente online!

(4 bytes salvos por @Dennis, que apontou que Jelly tinha uma "soma da diagonal principal" embutida. Eu não esperava que ela tivesse um desses; a solução anterior implementou a operação sem usar o embutido. A operação em questão, Æṭ, é definido como "traço", mas o traço é definido apenas para matrizes quadradas; o Jelly também implementa uma generalização para matrizes retangulares.)

A melhoria em relação às outras respostas é principalmente de um algoritmo mais simples (portanto, terser para expressar); esse programa foi originalmente escrito no Brachylog v2 ( {\p\iᶠ∋₎ᵐ+}ᶠot), mas o Jelly possui alguns componentes internos para partes do programa que precisam ser explicadas no Brachylog, então isso ficou mais curto.

Explicação

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

Deve ficar claro que, para qualquer solução para o problema, podemos permutar as colunas da matriz original para colocar essa solução na diagonal principal. Portanto, essa solução simplesmente inverte isso, encontrando todas as principais diagonais principais possíveis de permutações.

Observe que a operação "permutar as colunas" é feita como "transpor, permutar as linhas" sem se preocupar em transpor de volta; o restante do algoritmo é simétrico em relação à diagonal principal; portanto, não precisamos desfazer a transposição e, portanto, podemos salvar um byte.

J , 28 bytes

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

Experimente online!

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

Aqui a chamada recursiva é feita pela $:qual representa a maior função anônima que a contém. Temos sorte em J de ter o primitivo x u\. y, que se aplica ua "outfixes" sucessivos yobtidos, suprimindo infixes sucessivos de comprimento xdos itens em y; aqui, queremos suprimir colunas sucessivas para obter "menores", para que transponha |:as linhas inferiores (ou cauda }.) de ye depois recuamos na transposição de seus outfixes.

Python 3 , 94 90 89 84 80 bytes

^{-4 bytes graças ao xnor (usando conjuntos em vez de listas)!}

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

Experimente online!

Husk , 12 11 9 bytes

▲mȯΣ►L∂PT

Experimente online!

Graças ao BMO por sugerir uma porta da resposta do ais523 e um salvamento de 2 bytes, que eu consegui melhorar ainda mais e, por sua vez, o BMO eliminou mais 2 bytes.

---

Solução anterior (14 bytes)

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

Experimente online!

Não pude fazer uma suíte de testes porque esta resposta usa o primeiro argumento de linha de comando explicitamente comando. Mas Husk não usa STDIN, por isso incluí todos os casos de teste, para que você possa copiar e colar no campo de argumento para verificar. Observe também que matrizes no Husk podem não conter espaços entre os elementos enquanto são inseridas.

Como funciona?

Repartição do código

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

Exemplo

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

É preciso escolher exatamente um índice de cada um, de modo que não haja dois índices correspondentes. Portanto, geramos os intervalos de comprimento das linhas e mantemos apenas aqueles sem duplicatas, produzindo as seguintes combinações (cada combinação é uma coluna em vez de uma linha para economizar espaço):

$$\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)$$

Em seguida, o programa indexa nas listas de entrada com cada elemento da combinação, retornando:

$$\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 bytes

Obrigado a @tsh por identificar 2 bytes inúteis que foram usados ​​para corrigir um erro.
Salva 3 bytes graças a @tsh

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

Experimente online!

Geléia , 13 12 bytes

ẈŒpQƑƇị"€¹§Ṁ

Experimente online!

Versão alternativa, 11 bytes

ZLœ!Lị"€¹§Ṁ

Isso usa o novo recurso œ!incorporado, que gera todas as permutações de um determinado comprimento.

Experimente online!

Como funciona

ẈŒ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 bytes

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

Experimente online!

Explicação e Não Goleado

A função take i<>drop(i+1)recebe uma lista e remove o elemento na posição i.

A função fobtém cada elemento possível ena posição i, remove os elementos na posição idos elementos restantes e adiciona eao ótimo recursivamente calculado:

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

E o caso base para a lista vazia é apenas 0:

f _=0

Braquilog , 18 bytes

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

Experimente online!

Explicação

                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 bytes

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

Experimente online!

Decentemente curto, apesar da longa permutationsligação. Este é um bloco de código anônimo que pega uma lista de listas e retorna um número.

Explicação:

{                                               } # 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 bytes

-13 bytes graças a ngn!

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

Experimente online!

Solução inicial:

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

Experimente online!

Nota: Não funciona para o primeiro caso de teste [[1]]

Explicação:

{ } - função com argumento 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 bytes

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

Experimente online!

---

71 bytes

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

Experimente online!

As [x|x<-a,y<-a,x==y]==averificações das quais os elementos asão distintos. Isso usa um número surpreendente de caracteres, mas não vi uma maneira mais curta.

Pitão, 15 12 bytes

[email protected]

Experimente online aqui .

[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

Editar: salvou 3 bytes, cortesia de issacg

05AB1E , 18 13 bytes

нgLœε‚øε`è]OZ

Tenho a sensação de que é muito longo, mas não tenho certeza de como fazer a indexação vetorial byte com eficiência em 05AB1E .. E eu estava certo de que era muito longo .. -5 bytes graças a @Emigna .

Experimente online ou verifique todos os casos de teste .

Explicação:

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

Exemplo de execução:

• Entrada: [[1,4,2],[5,6,1]]
• Após o passo 1 ( нgL):[1,2,3]
• Após o passo 2 ( œ):[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
• Após o passo 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]]]
• Após o passo 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]]]
• Após a etapa 5 ( ε`è]): [[4,1],[4,5],[2,6],[2,5],[1,6],[1,1]](OBSERVAÇÃO: 05AB1E é indexada em 0 (com envolvimento automático), portanto, a indexação 3em [5,6,1]resultados é 5.)
• Após o passo 6 ( O):[5,9,8,7,7,2]
• Saída / após o passo 7 ( à):9

Haskell, 84 bytes

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

Experimente online!

Ruby , 74 72 69 bytes

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

Experimente online!

05AB1E , 7 bytes

øœ€Å\Oà

Porta da resposta Jelly CW de @ ais523 , por isso não deixe de votar também!

Experimente online ou verifique todos os casos de teste .

Explicação:

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