Finden Sie die Submatrix mit dem kleinsten Mittelwert, 2.0

15

Sie erhalten eine n-mal-m- Matrix von ganzen Zahlen, wobei n, m> 3 ist . Ihre Aufgabe ist es, die 3-mal-3 -Submatrix mit dem niedrigsten Mittelwert zu finden und diesen Wert auszugeben.

Regeln und Erläuterungen:

  • Die ganzen Zahlen sind nicht negativ
  • Optionales Eingabe- und Ausgabeformat
  • Die Ausgabe muss bis auf mindestens 2 Dezimalpunkte genau sein (wenn es sich um eine nicht ganzzahlige Zahl handelt)
  • Die Submatrizen können aus beliebigen Spalten und Zeilen bestehen

Testfälle:

1   0   4   0   1   0
1   0   4   0   1   0
4   3   4   3   4   3
1   0   4   0   1   0

Minimum mean: 0   (We have chosen columns 2,4,6 and rows 1,2,4 (1-indexed)
-----------------------------
4    8    9    7
5   10    1    5
8    5    2    4
8    3    5   10
6    6    3    4

Minimum mean: 4.2222
-----------------------------
1   0   0   0   0
0   2   0   0   0
0   0   3   0   0
0   0   0   4   0
0   0   0   0   5

Minimum mean: 0.11111
-----------------------------
371   565   361   625   879   504   113   104
943   544   157   799   726   832   228   405
743   114   171   506   943   181   823   454
503   410   333   735   554   227   423   662
629   439   191   707    52   751   506   924

Minimum mean: 309.56
code-golf math matrix Stewie Griffin
quelle
Was unterscheidet das von der ersten Version dieser Herausforderung?
Kritixi Lithos
2
@KritixiLithos Verwendet die allgemeinere Definition von "Untermatrix", wobei eine Untermatrix eine Matrix ist, die Sie durch Löschen einer beliebigen Anzahl von Zeilen und Spalten aus dem Original erhalten können (sodass die verbleibenden Zeilen / Spalten nicht benachbart sein müssen).
Martin Ender

Antworten:

9

Mathematica, 77 50 Bytes

±x_:=x~Subsets~{3}
Min[Mean/@Mean/@±#&/@±#]&

ist der Transpositionsoperator von Mathematica (und wird in Mathematica als hochgestelltes T gerendert).

Diese Antwort definiert zuerst einen Hilfsoperator, ±der alle 3-Element-Teilmengen einer Liste zurückgibt und dann zu einer unbenannten Funktion ausgewertet wird, die diesen Operator zur Lösung des Problems verwendet.

Dazu werden zunächst alle 3-Element-Teilmengen der Zeilen der Matrix berechnet. Dann transponieren wir für jede solche Teilmenge diese und berechnen ihre 3-Element-Teilmenge von Zeilen. Dies gibt uns alle möglichen 3x3 Submatrizen (obwohl sie transponiert sind). Wir berechnen dann den Mittelwert für alle von ihnen und finden das Gesamtminimum.

Martin Ender
quelle
7

Jelly , 15 12 Bytes

œc3S€Zµ⁺FṂ÷9

Probieren Sie es online!

Wie es funktioniert

œc3S€Zµ⁺FṂ÷9  Main link. Argument: M (matrix)

œc3           Yield all combinations of 3 rows.
   S€         Map column-wise sum over the combinations.
     Z        Zip, transposing rows and columns.
      µ       Combine all links to the left into a chain.
       ⁺      Duplicate the chain, executing it twice.
        F     Flatten.
         Ṃ    Take the minimum.
          ÷9  Divide it by 9.
Dennis
quelle
œc3S€µ⁺€FṂ÷9ist, was ich habe ... EDIT - hah und einfach so machst du das gleiche: D
Jonathan Allan
Ninja'd um 17 Sekunden. : P Trotzdem danke. :)
Dennis
Ich kann nicht anders, als zu glauben, dass es einen Weg gibt, das 9durch Teilen durch 3innerhalb der wiederholten Kette loszuwerden , aber ist es möglich, 3das richtige Argument zu finden, so dass es in 11 möglich ist?
Jonathan Allan
Nicht in einem Byte, und das wäre nötig, um eines zu retten. Sie können 3 nicht außerhalb der Kette platzieren (beides, weil es monadisch ist und Sie es gruppieren müssten, um es zu verwenden ⁺), und innerhalb der Kette müssen Sie entweder 3explizit angeben oder es mit gruppieren ÷.
Dennis
4

05AB1E , 21 16 Bytes

2Fvyæ3ùO})ø}˜9/W

Probieren Sie es online!

Erläuterung

  • Erhalten Sie für jede Zeile die Summe jeder bestellten Teilmenge der Größe 3
  • Transponiere die resultierende Matrix
  • Erhalten Sie für jede Zeile die Summe jeder bestellten Teilmenge der Größe 3
  • Reduzieren Sie die resultierende Matrix
  • Teilen Sie durch 9
  • Holen Sie sich das Minimum
Emigna
quelle
1

Haskell , 90 Bytes

import Data.List
t r=[a+b+c|[a,b,c]<-subsequences r]
s=(/9).minimum.(t=<<).transpose.map t

Probieren Sie es online!

Roman Czyborra
quelle
1
concatMap tkann verkürzt werden auf(>>=t)
Laikoni
0

Bean , 198 Bytes

Hexdump:

00000000 bc 81 bd a0 65 40 a0 5d dd a0 68 50 80 a0 77 20  ¼.½ e@ ]Ý hP. w 
00000010 80 01 dd a0 66 25 3b 52 cc cb c0 50 84 a0 5d 20  ..Ý f%;RÌËÀP. ] 
00000020 66 87 4c cc a0 68 8b 20 66 8c 25 3b cd d0 84 a0  f.LÌ h. f.%;ÍÐ. 
00000030 5d 20 66 80 4e a0 66 81 4c d3 a0 65 a0 5d a0 68  ] f.N f.LÓ e ] h
00000040 4c a0 66 8c 25 3a 8b 25 3a 50 84 a0 5d 20 66 bd  L f.%:.%:P. ] f½
00000050 a0 6e 43 a5 39 a5 3a a5 3b 00 bd a0 5f 43 cf 20   nC¥9¥:¥;.½ _CÏ 
00000060 6e 00 3d a0 69 20 12 b6 a7 36 a7 26 4d a0 69 80  n.= i .¶§6§&M i.
00000070 53 d0 80 a0 1f 20 80 45 a0 69 53 d0 80 a0 6e 20  SÐ. . .E iSÐ. n 
00000080 80 8b 40 a0 6f a0 75 4c a0 6f 8b 53 d0 80 a0 5f  ..@ o uL o.SÐ. _
00000090 20 80 8b 40 a0 6f a0 74 4c a0 6f 8b 50 84 d0 84   ..@ o tL o.P.Ð.
000000a0 a0 77 20 75 20 74 4c d3 a0 65 a0 5f 50 80 a0 43   w u tLÓ e _P. C
000000b0 20 80 01 81 25 3b 4c d3 a0 65 20 6e 81 25 3b 26   ...%;LÓ e n.%;&
000000c0 4c a0 69 8e 25 42                                L i.%B
000000c6

Entsprechendes JavaScript:

// indices array increment function
var i=(a,l=$.length,j=2)=>++a[j]>=l+j-2?a[j]=j&&i(a,l,j-1)+1:a[j],
// row indices
    r=[0,1,2],
// column indices
    c=[...r],
// minimum sum
    m=Infinity;
do{
  do{
// calculate sum of current row/column indices and keep minimum
    m=Math.min(m,
      (r.reduce((s,y)=>s+c.reduce((s,x)=>s+$[y][x])))
    )
// until column indices loop
  }while(i(c,A.length)!=2)
// until row indices loop
}while(i(r)!=2)
// output mean
m/9

Probieren Sie die Demo hier aus

Patrick Roberts
quelle