Неперекрывающаяся матричная сумма

Для заданных k массивов длины n выведите максимально возможную сумму, используя один элемент из каждого массива, чтобы не было двух элементов с одинаковым индексом. Гарантируется, что k <= n.

вход

Непустой список непустых массивов целых чисел.

Выход

Целое число, представляющее максимальную сумму.

Примеры

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

Желе , 10 6 байт

ZŒ!ÆṭṀ

Попробуйте онлайн!

(4 байта, сохраненные @Dennis, который указал, что у Jelly была встроенная «сумма главной диагонали». Я не ожидал, что у него будет один из них; предыдущее решение реализовало операцию без использования встроенной функции. Æṭ, определяется как «трассировка», но трассировка определяется только для квадратных матриц; Jelly также осуществляет обобщение для прямоугольных матриц.)

Улучшение по сравнению с другими ответами в основном за счет более простого (а значит, более выразительного) алгоритма; эта программа изначально была написана в Brachylog v2 ( {\p\iᶠ∋₎ᵐ+}ᶠot), но у Jelly есть некоторые встроенные функции для частей программы, которые должны быть прописаны в Brachylog, так что это оказалось короче.

объяснение

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

Должно быть ясно, что для любого решения проблемы мы можем переставить столбцы исходной матрицы, чтобы поместить это решение на основную диагональ. Таким образом, это решение просто переворачивает это, находя все возможные главные диагонали перестановок.

Обратите внимание, что операция «перестановка столбцов» выполняется как «транспонировать, переставлять строки», не заботясь о транспонировании назад; остальная часть алгоритма оказывается симметричной относительно главной диагонали, поэтому нам не нужно отменять транспонирование и, таким образом, можно сохранить байт.

J , 28 байт

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

Попробуйте онлайн!

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

Здесь выполняется рекурсивный вызов, $:который представляет наибольшую анонимную функцию, содержащую ее. Нам повезло, что в J есть примитив x u\. y, который применяется uк последовательным «наложениям», yполученным путем подавления последовательных инфиксов длины xэлементов в y; здесь мы хотим превзойти последовательные столбцы, чтобы получить «миноры», поэтому мы транспонируем |:нижние строки (или хвост }.) y, а затем возвращаемся к транспонированию их дополнений.

Python 3 , 94 90 89 84 80 байт

^{-4 байта благодаря xnor (используя наборы вместо списков)!}

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

Попробуйте онлайн!

Шелуха , 12 11 9 байт

▲mȯΣ►L∂PT

Попробуйте онлайн!

Спасибо BMO за предложение порта ответа ais523 и 2-байтового сохранения, которое мне удалось улучшить в дальнейшем, и, в свою очередь, BMO сбило еще 2 байта.

---

Предыдущее решение (14 байт)

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

Попробуйте онлайн!

Я не смог сделать тестовый набор, потому что этот ответ использует явно первую команду аргумента командной строки . Но Husk вообще не использует STDIN, поэтому я включил все тестовые примеры, так что вы можете просто скопировать вставить в поле аргумента, чтобы проверить его. Также обратите внимание, что массивы в Husk могут не содержать пробелов между элементами при вводе.

Как это работает?

Разбивка кода

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

пример

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

Нужно выбрать ровно один индекс из каждого так, чтобы никакие два индекса не соответствовали. Итак, мы генерируем диапазоны длин строк и оставляем только те, у которых нет дубликатов, получая следующие комбинации (каждая комбинация представляет собой столбец вместо строки для экономии места):

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

Затем программа индексирует во входных списках каждый элемент комбинации, возвращая:

$$\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 байт

Спасибо @tsh за выявление 2 бесполезных байтов, которые были использованы для исправления ошибки.
Сохранено 3 байта благодаря @tsh

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

Попробуйте онлайн!

Желе , 13 12 байт

ẈŒpQƑƇị"€¹§Ṁ

Попробуйте онлайн!

Альтернативная версия, 11 байт

ZLœ!Lị"€¹§Ṁ

Это использует недавно добавленный œ! встроенная функция, которая генерирует все перестановки заданной длины.

Попробуйте онлайн!

Как это работает

ẈŒ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 байт

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

Попробуйте онлайн!

Объяснение и Унгольфед

Функция take i<>drop(i+1)берет список и удаляет элемент в позицииi .

Функция fполучает каждый возможный элемент eв позиции i, удаляет элементы в позиции iиз оставшихся элементов и добавляет eк рекурсивно вычисленному оптимуму:

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

И базовый вариант для пустого списка просто 0:

f _=0

Брахилог , 18 байт

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

Попробуйте онлайн!

объяснение

                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 байтов

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

Попробуйте онлайн!

Достойно короткий, даже несмотря на длинный permutations звонок. Это блок анонимного кода, который принимает список списков и возвращает число.

Объяснение:

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

К (ок) , 40, 32, 28, 19 байтов

-13 байт благодаря ngn!

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

Попробуйте онлайн!

Начальное решение:

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

Попробуйте онлайн!

Примечание: не работает для первого теста [[1]]

Объяснение:

{ } - функция с аргументом 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 байт

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

Попробуйте онлайн!

---

71 байт

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

Попробуйте онлайн!

В [x|x<-a,y<-a,x==y]==aпроверяет , что элементы aразличны. Это использует удивительное количество символов, но я не видел более короткого пути.

Pyth, 15 12 байт

eSms@VQd.plh

Попробуйте это онлайн здесь .

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

Редактировать: сохранено 3 байта предоставлено issacg

05AB1E , 18 13 байт

нgLœε‚øε`è]OZ

У меня такое ощущение, что он слишком длинный, но я не уверен, как эффективно выполнять векторизованное индексирование байтов в 05AB1E .. И я действительно был прав, что он был слишком длинным .. -5 байт благодаря @Emigna .

Попробуйте онлайн или проверьте все контрольные примеры .

Объяснение:

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

Пример выполнения:

• Входные данные: [[1,4,2],[5,6,1]]
• После шага 1 ( нgL):[1,2,3]
• После шага 2 ( œ):[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
• После шага 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]]]
• После шага 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]]]
• После шага 5 ( ε`è]): [[4,1],[4,5],[2,6],[2,5],[1,6],[1,1]](ПРИМЕЧАНИЕ: 05AB1E индексируется 0 (с автоматическим переносом), поэтому индексация 3в [5,6,1]результаты5 .)
• После шага 6 ( O):[5,9,8,7,7,2]
• Вывод / после шага 7 ( à):9

Haskell, 84 байта

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

Попробуйте онлайн!

Рубин , 74 72 69 байт

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

Попробуйте онлайн!

05AB1E , 7 байтов

øœ€Å\Oà

Ответ от Jelly CW от @ ais523 , так что не забудьте также заявить об этом!

Попробуйте онлайн или проверьте все контрольные примеры .

Объяснение:

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