25
\$\begingroup\$

Non-overlapping Matrix Sum

Given k arrays of length n, output the maximum sum possible using one element from each array such that no two elements are from the same index. It is guaranteed that k<=n.

Input

A nonempty list of nonempty arrays of integers.

Output

An integer that represents the maximum sum.

Examples

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
\$\endgroup\$
  • 5
    \$\begingroup\$ Math fun fact: For square arrays, this is the matrix permanent over the tropical semiring which uses the operations (max, +) in place of (+, *). \$\endgroup\$ – xnor Dec 18 '18 at 22:00

16 Answers 16

9
\$\begingroup\$

Jelly, 10 6 bytes

ZŒ!ÆṭṀ

Try it online!

(4 bytes saved by @Dennis, who pointed out that Jelly had a "sum of main diagonal" builtin. I was not expecting it to have one of those; the previous solution implemented the operation without using the builtin. The operation in question, Æṭ, is defined as "trace", but the trace is only defined for square matrices; Jelly implements a generalisation to rectangular matrices too.)

The improvement over the other answers is mostly from a simpler (thus terser to express) algorithm; this program was originally written in Brachylog v2 ({\p\iᶠ∋₎ᵐ+}ᶠot), but Jelly has some builtins for parts of the program that have to be spelled out in Brachylog, so this came out shorter.

Explanation

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

It should be clear that for any solution to the problem, we can permute the columns of the original matrix to put that solution onto the main diagonal. So this solution simply reverses that, finding all possible main diagonals of permutations.

Note that the "permute the columns" operation is done as "transpose, permute the rows" without bothering to transpose back; the rest of the algorithm happens to be symmetrical about the main diagonal, so we don't need to undo the transpose and thus can save a byte.

\$\endgroup\$
  • \$\begingroup\$ ZŒ!ÆṭṀ saves four bytes. Try it online! \$\endgroup\$ – Dennis Dec 18 '18 at 0:09
  • \$\begingroup\$ Well it looks like Dennis got the last word in :P \$\endgroup\$ – Quintec Dec 18 '18 at 1:09
  • \$\begingroup\$ I wonder if that builtin's ever come up before? \$\endgroup\$ – ais523 Dec 18 '18 at 2:42
  • \$\begingroup\$ Not sure, but probably not. I actually suggested ZŒ!ŒD§ṀḢ before remembering that Æṭ was a thing. \$\endgroup\$ – Dennis Dec 18 '18 at 2:44
8
\$\begingroup\$

J, 28 bytes

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

Try it online!

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

Here the recursive call is done by $: which represents the largest anonymous function containing it. We are lucky in J to have the primitive x u\. y, which applies u to successive "outfixes" of y obtained by suppressing successive infixes of length x of the items in y; here we want to surpress successive columns to get "minors", so we transpose |: the lower rows (or tail }.) of y, and then recurse on the transpose of their outfixes.

\$\endgroup\$
  • 2
    \$\begingroup\$ Hi and welcome to PPCG! I added a Try it online link for your solution, so that others can verify it. \$\endgroup\$ – Galen Ivanov Dec 17 '18 at 9:01
7
\$\begingroup\$

Python 3, 94 90 89 84 80 bytes

-4 bytes thanks to xnor (using sets instead of lists)!

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Nice method! You can make y a set to shorten the membership check: f=lambda x,y={-1}:x>[]and max(e+f(x[1:],y|{i})for(i,e)in enumerate(x[0])if{i}-y). \$\endgroup\$ – xnor Dec 17 '18 at 6:08
  • \$\begingroup\$ @xnor: That -1 trick is really clever :) Thanks a lot! \$\endgroup\$ – ბიმო Dec 17 '18 at 16:49
7
\$\begingroup\$

Husk, 12 11 9 bytes

▲mȯΣ►L∂PT

Try it online!

Thanks to BMO for suggesting a port of ais523's answer and a 2-byte save, which I managed to improve on further, and in turn BMO shaved off 2 more bytes.


Previous solution (14 bytes)

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

Try it online!

I wasn't able to make a test suite because this answer uses the first command line argument command explicitly. But Husk doesn't use STDIN at all so I included all the test cases there, so you can just copy paste in the argument field to check it out. Also note that arrays in Husk may not contain spaces between elements while being inputted.

How it works?

Code breakdown

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

Example

Let's pick an example: $$\left(\begin{matrix}1&4&2\\5&6&1\end{matrix}\right)$$

One must pick exactly one index from each such that no two indices correspond. So, we generate the length ranges of the rows and only keep those without duplicates, yielding the following combinations (each combination is a column instead of a row to save space):

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

Then, the program indexes in the input lists with each element of the combination, returning:

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

Summing all those results (here, each column, for the aforementioned reason), one obtains all possible valid sums according to the criteria, in this case \$9\$.

\$\endgroup\$
5
\$\begingroup\$

JavaScript (ES6),  74  71 bytes

Thanks to @tsh for identifying 2 useless bytes that were used to fix a bug
Saved 3 bytes thanks to @tsh

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ @Shaggy but it is impossible to compose 0 from input array, -1+(-1) is -2 and it is correct answer. \$\endgroup\$ – val Dec 17 '18 at 9:56
  • 1
    \$\begingroup\$ f=([a,...r],k,i=1)=>a?Math.max(...a.map(c=>k&(i+=i)?-1/0:c+f(r,k|i))):0 It's strange, but Math.max saves bytes... \$\endgroup\$ – tsh Dec 17 '18 at 10:40
4
\$\begingroup\$

Jelly, 13 12 bytes

ẈŒpQƑƇị"€¹§Ṁ

Try it online!

Alternate version, 11 bytes

ZLœ!Lị"€¹§Ṁ

This uses the newly added œ! built-in, which generates all permutations of a given length.

Try it online!

How it works

ẈŒ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.
\$\endgroup\$
  • \$\begingroup\$ Ah... I almost posted this same answer with XLṗL instead of J€Œp. \$\endgroup\$ – Erik the Outgolfer Dec 16 '18 at 22:48
4
\$\begingroup\$

Haskell, 65 bytes

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

Try it online!

Explanation & Ungolfed

The function take i<>drop(i+1) takes a list and removes the element at position i.

The function f gets each possible element e at position i, removes the elements at position i from the remaining elements and adds e to the recursively computed optimum:

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

And the base case for the empty list is just 0:

f _=0
\$\endgroup\$
2
\$\begingroup\$

Brachylog, 18 bytes

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

Try it online!

Explanation

                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
\$\endgroup\$
2
\$\begingroup\$

Perl 6, 50 49 bytes

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

Try it online!

Decently short, even despite the long permutations call. This is an anonymous code block that takes a list of lists and returns a number.

Explanation:

{                                               } # 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
\$\endgroup\$
2
\$\begingroup\$

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

-13 bytes thanks to ngn!

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

Try it online!

Initial solution:

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

Try it online!

Note: Doesn't work for the first test case [[1]]

Explanation:

{ } - function with 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
\$\endgroup\$
  • 1
    \$\begingroup\$ hint: prm can be applied directly to a list to generate its permutations \$\endgroup\$ – ngn Dec 18 '18 at 7:30
  • \$\begingroup\$ @ngn Thanks! I wanted to use the main diagonal with =, but the result was longer. Is there flatten in oK? \$\endgroup\$ – Galen Ivanov Dec 18 '18 at 9:32
  • \$\begingroup\$ flatten in what sense? \$\endgroup\$ – ngn Dec 18 '18 at 9:33
  • \$\begingroup\$ @ngn (1 2 3; 4 5 6; 7 8 9) -> (1 2 3 4 5 6 7 8 9) \$\endgroup\$ – Galen Ivanov Dec 18 '18 at 9:38
  • 1
    \$\begingroup\$ that's just ,/ or if you want it to go into deeper structures: ,// \$\endgroup\$ – ngn Dec 18 '18 at 9:42
2
\$\begingroup\$

Haskell, 65 bytes

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

Try it online!


71 bytes

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

Try it online!

The [x|x<-a,y<-a,x==y]==a checks that the elements of a are distinct. This uses up a surprising number of characters, but I didn't see a shorter way.

\$\endgroup\$
1
\$\begingroup\$

Pyth, 15 12 bytes

eSms@VQd.plh

Try it online here.

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

Edit: saved 3 bytes courtesy of issacg

\$\endgroup\$
  • 1
    \$\begingroup\$ .PUlhQl can be replaced by .plh. V implicitly ignores any extra entries. \$\endgroup\$ – isaacg Dec 18 '18 at 1:06
1
\$\begingroup\$

05AB1E, 18 13 bytes

нgLœε‚øε`è]OZ

I have the feeling it's overly long, but I'm not sure how to do vectorized indexing byte-efficiently in 05AB1E.. And I was indeed right that it was too long.. -5 bytes thanks to @Emigna.

Try it online or verify all test cases.

Explanation:

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

Example run:

  • Input: [[1,4,2],[5,6,1]]
  • After step 1 (нgL): [1,2,3]
  • After step 2 (œ): [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
  • After step 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]]]
  • After step 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]]]
  • After step 5 (ε`è]): [[4,1],[4,5],[2,6],[2,5],[1,6],[1,1]] (NOTE: 05AB1E is 0-indexed (with automatic wraparound), so indexing 3 into [5,6,1] results in 5.)
  • After step 6 (O): [5,9,8,7,7,2]
  • Output / after step 7 (à): 9
\$\endgroup\$
  • 1
    \$\begingroup\$ I had нgLœε‚øεè]OZ` for 13. \$\endgroup\$ – Emigna Dec 18 '18 at 8:32
  • \$\begingroup\$ @Emigna Thanks! It's surprisingly similar to what I had I see, except that I added a bunch of crap that was unnecessary. ;p \$\endgroup\$ – Kevin Cruijssen Dec 18 '18 at 8:43
1
\$\begingroup\$

Haskell, 84 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Ruby, 74 72 69 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

05AB1E, 7 bytes

øœ€Å\Oà

Port of @ais523's Jelly CW answer, so make sure to upvote it as well!

Try it online or verify all test cases.

Explanation:

ø          # 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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.