Somme de matrice sans chevauchement

Étant donné k tableaux de longueur n , affichez la somme maximale possible en utilisant un élément de chaque tableau de sorte qu'il n'y ait pas deux éléments du même index. Il est garanti que k <= n.

Contribution

Une liste non vide de tableaux non vides d'entiers.

Sortie

Un entier qui représente la somme maximale.

Exemples

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ée , 10 6 octets

ZŒ!ÆṭṀ

Essayez-le en ligne!

(4 octets enregistrés par @Dennis, qui a souligné que Jelly avait une "somme de la diagonale principale" intégrée. Je ne m'attendais pas à ce qu'elle en ait une; la solution précédente implémentait l'opération sans utiliser la fonction intégrée. L'opération en question, Æṭ, est défini comme "trace", mais la trace n'est définie que pour les matrices carrées; Jelly implémente également une généralisation aux matrices rectangulaires.)

L'amélioration par rapport aux autres réponses provient principalement d'un algorithme plus simple (donc terser pour exprimer); ce programme a été écrit à l'origine dans Brachylog v2 ( {\p\iᶠ∋₎ᵐ+}ᶠot), mais Jelly a quelques prédéfinis pour des parties du programme qui doivent être précisées dans Brachylog, donc cela est sorti plus court.

Explication

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

Il doit être clair que pour toute solution au problème, nous pouvons permuter les colonnes de la matrice d'origine pour mettre cette solution sur la diagonale principale. Donc, cette solution inverse simplement cela, en trouvant toutes les diagonales principales possibles de permutations.

Notez que l'opération "permuter les colonnes" se fait comme "transposer, permuter les lignes" sans prendre la peine de transposer en arrière; le reste de l'algorithme se trouve être symétrique par rapport à la diagonale principale, nous n'avons donc pas besoin d'annuler la transposition et pouvons donc enregistrer un octet.

J , 28 octets

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

Essayez-le en ligne!

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

Ici, l'appel récursif est effectué par $:lequel représente la plus grande fonction anonyme qui le contient. On a de la chance en J d'avoir la primitive x u\. y, qui s'applique uaux "outfixes" successifs de yobtenus en supprimant les infixes successifs de longueur xdes items en y; ici, nous voulons surpresser les colonnes successives pour obtenir des "mineurs", donc nous transposons |:les lignes inférieures (ou queue }.) de y, puis récursions sur la transposition de leurs outfixes.

Python 3 , 94 90 89 84 80 octets

^{-4 octets grâce à xnor (en utilisant des ensembles au lieu de listes)!}

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

Essayez-le en ligne!

Husk , 12 11 9 octets

▲mȯΣ►L∂PT

Essayez-le en ligne!

Merci à BMO d' avoir proposé un port de réponse à ais523 et une sauvegarde de 2 octets, que j'ai réussi à améliorer davantage, et à mon tour, BMO a réduit de 2 octets de plus.

---

Solution précédente (14 octets)

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

Essayez-le en ligne!

Je n'ai pas pu créer de suite de tests car cette réponse utilise explicitement la première commande d'argument de ligne de commande. Mais Husk n'utilise pas du tout STDIN, j'ai donc inclus tous les cas de test là-bas, vous pouvez donc simplement copier-coller dans le champ d'argument pour le vérifier. Notez également que les tableaux dans Husk peuvent ne pas contenir d'espaces entre les éléments lors de leur entrée.

Comment ça marche?

Répartition du code

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

Exemple

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

Il faut choisir exactement un indice dans chacun de sorte qu'il n'y ait pas deux indices correspondant. Ainsi, nous générons les plages de longueur des lignes et ne gardons que celles sans doublons, ce qui donne les combinaisons suivantes (chaque combinaison est une colonne au lieu d'une ligne pour économiser de l'espace):

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

Ensuite, le programme indexe dans les listes d'entrée avec chaque élément de la combinaison, retournant:

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

Merci à @tsh d'avoir identifié 2 octets inutiles qui ont été utilisés pour corriger un bug.
Sauvegardé 3 octets grâce à @tsh

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

Essayez-le en ligne!

Gelée , 13 12 octets

ẈŒpQƑƇị"€¹§Ṁ

Essayez-le en ligne!

Version alternative, 11 octets

ZLœ!Lị"€¹§Ṁ

Celui-ci utilise le module œ!intégré nouvellement ajouté , qui génère toutes les permutations d'une longueur donnée.

Essayez-le en ligne!

Comment ça marche

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

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

Essayez-le en ligne!

Explication et non golfé

La fonction take i<>drop(i+1)prend une liste et supprime l'élément en position i.

La fonction fobtient chaque élément possible een position i, supprime les éléments en position ides éléments restants et ajoute eà l'optimum calculé récursivement:

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

Et le cas de base pour la liste vide est juste 0:

f _=0

Brachylog , 18 octets

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

Essayez-le en ligne!

Explication

                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 octets

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

Essayez-le en ligne!

Décemment court, malgré le long permutationsappel. Il s'agit d'un bloc de code anonyme qui prend une liste de listes et renvoie un nombre.

Explication:

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

-13 octets grâce à ngn!

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

Essayez-le en ligne!

Solution initiale:

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

Essayez-le en ligne!

Remarque: ne fonctionne pas pour le premier cas de test [[1]]

Explication:

{ } - fonction avec argument 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 octets

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

Essayez-le en ligne!

---

71 octets

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

Essayez-le en ligne!

Les [x|x<-a,y<-a,x==y]==acontrôles dont les éléments asont distincts. Cela utilise un nombre surprenant de caractères, mais je n'ai pas vu un moyen plus court.

Pyth, 15 12 octets

[email protected]

Essayez-le en ligne ici .

[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

Edit: enregistré 3 octets avec l'aimable autorisation de issacg

05AB1E , 18 13 octets

нgLœε‚øε`è]OZ

J'ai l'impression que c'est trop long, mais je ne sais pas comment faire une indexation vectorisée de manière efficace dans 05AB1E .. Et j'avais en effet raison que c'était trop long .. -5 octets grâce à @Emigna .

Essayez-le en ligne ou vérifiez tous les cas de test .

Explication:

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

Exemple d'exécution:

• Contribution: [[1,4,2],[5,6,1]]
• Après l'étape 1 (нgL ):[1,2,3]
• Après l'étape 2 (œ ):[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
• Après l'étape 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]]]
• Après l'étape 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]]]
• Après l'étape 5 ( ε`è]): [[4,1],[4,5],[2,6],[2,5],[1,6],[1,1]](REMARQUE: 05AB1E est indexé 0 (avec habillage automatique), donc l'indexation3 en [5,6,1]résulte en5 .)
• Après l'étape 6 (O ):[5,9,8,7,7,2]
• Sortie / après l'étape 7 ( à):9

Haskell, 84 octets

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

Essayez-le en ligne!

Rubis , 74 72 69 octets

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

Essayez-le en ligne!

05AB1E , 7 octets

øœ€Å\Oà

Réponse de Jelly CW du port de @ ais523 , alors assurez-vous de voter également!

Essayez-le en ligne ou vérifiez tous les cas de test .

Explication:

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