Find the representative submatrix

Question

Note: This is a more limited version of a challenge from 2014 that only received one answer. That challenge required participants write two programs; this challenge is essentially one half of that. The text here is original, but credit for the idea goes to Matthew Butterick, who is no longer active on the site.

Given a matrix of integers \$M\$, find the smallest (by number of elements) submatrix \$N\$ that contains at least one of every element present in \$M\$. (A submatrix is a “matrix formed by taking a block of the entries … from the original matrix.”)

$$ M = \begin{bmatrix}9 & 0 & -4 & 5 & 1 & -4\\ 3 & -2 & 5 & 9 & -7 & 1\\ \color{blue}{0} & \color{blue}{-7} & \color{blue}{-2} & \color{blue}{5} & 9 & 5\\ \color{blue}{9} & \color{blue}{9} & \color{blue}{5} & \color{blue}{-4} & 1 & 9\\ \color{blue}{-4} & \color{blue}{1} & \color{blue}{8} & \color{blue}{3} & -4 & -4\end{bmatrix} $$

In the above example the submatrix \$N\$, shown in blue, has at least one of every element in \$M\$, and there is no smaller submatrix with that property. Note that some elements (i.e. \$8\$) do not exist outside of \$N\$ and some elements in \$N\$ are duplicated (i.e. \$9\$).

Input

Input will consist of a matrix \$M\$ in any convenient format. It will be at least \$1\times 1\$.

Output

Output may be either of:

1. The submatrix \$N\$ in any convenient format. If it's returned as a 1-dimensional list its dimensions must also be given.

2. The position of \$N\$ within \$M\$, given either as the row and column positions of two of its corners diagonal from each other, or as the row and column position of one of its corners and its width and height. The answer should indicate which corners are given.

If multiple submatrices are tied for smallest representative submatrix, any one may be returned, or all may be returned.

Rules

• Default I/O rules and standard rules apply. Standard loopholes are forbidden.

• This is code-golf; shortest solution in bytes wins.

Test cases

The below test cases each show one possible correct output, but not all possible valid outputs.

Input

 3  3 -9  0  3
 3  3  1 -8  1
 0  0  0  8 -8
 3  8  8  0  3
 0  8  8  0 -9

Output

-8  1
 8 -8
 0  3
 0 -9

Input

 3  6 -8 -1
-8  3  1 -2
-8 -2 -1 -2

Output

 6 -8
 3  1
-2 -1

Input

-8 -7 -4  7 -7
-7 -6  7 -7 -7
 8 -3 -8 -6 -4
-4  5 -7  7  8
-8  7  8 -4 -3

Output

-3 -8 -6 -4
 5 -7  7  8

Input

-8  7
-2 -4

Output

-8  7
-2 -4

Answer 1

Python 3, ^{275 261 231 229 227 220 218} 201 bytes

def f(m):
 z,o,a,r=m,len,sum,range
 for i,k,j,l in product(*(r(o(m[0])),r(o(m)))*2):
  s=[q[i:j+1]for q in m[k:l+1]];t,f=a(s,[]),a(z,[])
  if{*f}=={*t}and o(t)<o(f):z=s
 return z
from itertools import*

Try it online!

• -14 thanks to Neil
• -30, -2, -17 thanks to okie

Input/output as nested lists.

Python 3 + golfing-shortcuts, ^{228 198 190 186} 164 bytes

def F(M):
 Z=M
 for I,K,J,L in Ip(*(r(l(M[0])),r(l(M)))*2):
  S=[Q[I:J+1]for Q in M[K:L+1]];T,F=s(S,[]),s(Z,[])
  if{*F}=={*T}and l(T)<l(F):Z=S
 p(Z)
from s import*

• -30, -22 thanks to okie

Makes use of the much cheaper s.Ip instead of itertools.product.

Answer 2

Jelly, 17 bytes

ZẆ$⁺€ẎFQL;LN$Ʋ$ÞṪ

A monadic Link that accepts the matrix as a list of lists and yields the/a smallest sub-matrix which contains all of the distinct values.

Try it online!

How?

ZẆ$⁺€ẎFQL;LN$Ʋ$ÞṪ - Link: rectangular matrix, M
  $               - last two links as a monad - f(X=M):
Z                 -   transpose
 Ẇ                -   all non-empty contiguous sub-lists (includes X itself (transposed))
    €             - for each (such "strip" of columns):
   ⁺              -   repeat the last link - i.e. f(X=strip)
     Ẏ            - tighten (to a flat list of the sub-matrices)
               Þ  - sort (these submatrices, S) by:
              $   -   last two links as a monad - g(S):
      F           -     flatten (S) -> Elements
             Ʋ    -     last four links as a monad - g(Elements):
       Q          -       deduplicate -> distinct elements
        L         -       length -> number of distinct elements
            $     -       last two links as a monad - h(elements):
          L       -         length -> total number of elements
           N      -         negate -> -1 * total number of elements
         ;        -       concatenate -> [number of distinct elements, -1 * total number of elements]
                Ṫ - tail

Answer 3

Charcoal, 51 bytes

ＦＬθＦ⊕ιＦＬ⌊θＦ⊕λ⊞υＥ✂θκ⊕ι¹✂νμ⊕λ≔Φυ¬⁻ΣθΣιυ≔ＥυＬΣιθＩ§υ⌕θ⌊θ

Attempt This Online! Link is to verbose version of code. Explanation:

ＦＬθＦ⊕ιＦＬ⌊θＦ⊕λ

Loop over all of the possible submatrices.

⊞υＥ✂θκ⊕ι¹✂νμ⊕λ

Extract the submatrix to the predefined empty list.

≔Φυ¬⁻ΣθΣιυ

Filter out those submatrices that are not representative.

≔ＥυＬΣιθ

Get the sizes of all the submatrices.

Ｉ§υ⌕θ⌊θ

Output the matrix with the smallest size.

Note that Charcoal outputs each element on its own row with rows double-spaced from each other.

Answer 4

JavaScript (ES10), 160 bytes

f=(m,x=s=g=m=>new Set(q=m.flat()).size,y)=>m.map((r,j)=>r.map((_,i)=>1/x?g(m)>g(M=m.slice(y,j+1).map(r=>r.slice(x,i+1)))|(v=q.length)>s||(s=v,o=M):f(m,i,j)))&&o

Try it online!

Commented

f = (                // f is a recursive function taking:
  m,                 //   m[] = input matrix
  x =                //   x = current column
  s =                //   s = best score
  g = m =>           //   g = helper function taking a sub-matrix m[],
  new Set(           //       turning into a set ...
    q = m.flat()     //       ... a flattened array q[] made from m[]
  ).size,            //       and returning its size
  y                  //   y = current row
) =>                 //
m.map((r, j) =>      // for each row r[] at index j in m[]:
  r.map((_, i) =>    //   for each cell at index i in r[]:
    1 / x ?          //     if x is defined (2nd pass):
      g(m) >         //       if the number of distinct values in m[]
      g(             //       is greater than those of
        M =          //         the sub-matrix M[]
        m.slice(     //         located between (x, y) and (i, j)
          y, j + 1   //         built by using slices of the original
        ).map(r =>   //         matrix
          r.slice(   //
            x, i + 1 //
          )          //
        )            //
      ) |            //       or
      (v = q.length) //       the size v of the sub-matrix
      > s            //       is greater than the current best size,
      ||             //       then do nothing
      (s = v, o = M) //       otherwise, update the solution
    :                //     else (first pass):
      f(m, i, j)     //       do a recursive call with (x, y) = (i, j)
  )                  //   end of inner map()
) && o               // end of outer map(); return the solution

Answer 5

Brachylog, 13 bytes

cd;Lcpġ.&s\s\

Try it online!

Really slow.

Explanation

We first get the set of distinct elements of the matrix. We know that the submatrix contains at least these elements: we thus append an unknown amount of additional elements (Brachylog will try in increasing amounts until it finds a solution), we then permute them (until it finds a solution) and group them in sublists of equal lengths (trying different lengths until it finds a solution). We finally constrain this constructed sublist to actually be a sublist of the input.

Since what we’re doing is basically constructing all possible matrices which contain at least all distinct elements of the original one, and verify afterwards that it is a real submatrix of the input, you can guess why it’s really slow.

c               Concatenate the matrix into a list
 d              Remove duplicate values: we get elements that must be in the submatrix
  ;Lc           Append an unknown list L to this list
     p          Try any permutation
      ġ.        Try any grouping of elements into sublists of equal lengths; this is the output
        &s      Take a subset of consecutive rows of the input
          \     Transpose
           s    Take a subset of consecutive columns of this subset
            \   Transpose
                This must also be the output (i.e. the output is a submatrix of the input)

Answer 6

05AB1E, 34 32 bytes

˜©āãε`"€üÿø€üÿ".V}€`€`Σ˜g}.Δ˜®åP

Try it online or verify all test cases.

Explanation:

Step 1: similar as my 05AB1E answer for the Find the box by its corners challenge, get all possible blocks from the input-matrix:

˜             # Flatten the (implicit) input-matrix
 ©            # Store it in variable `®` (without popping)
  ā           # Push a list in the range [1,length] (without popping the list)
   ã          # Create all possible pairs of this list with the cartesian product
ε             # Map over each pair:
 `            #  Pop and push them both separated to the stack
  "€üÿø€üÿ"   #  Push this string, where both `ÿ` are filled with the two values
           .V #  Evaluate and execute it as 05AB1E code:
   €          #   Map over each row of the (implicit) input-matrix
    üA        #    Convert it into overlapping lists of size A
      ø       #   Zip/transpose; swapping rows/columns
       €      #   Map over each the list of lists
        üB    #    Convert it into overlapping lists of size B
}             # Close the map
 €`€`         # Flatten two levels down so we have a list of blocks of various sizes

Step 2: Find the smallest valid AxB block from this list and output it:

Σ             # Sort all AxB blocks by:
 ˜            #  Flatten the matrix to a single list
  g           #  Pop and push its length to get the amount of elements in this block
}.Δ           # After the sort-by: find the first/smallest block which is truthy for:
   ˜          #  Flatten the current AxB block
    ®         #  Push the flattened input-list from variable `®`
     å        #  Check for each value of the input-list if it's in the block-list
      P       #  Check if this is truthy for all of them
              # (after which this smallest found block is output implicitly as result)

Answer 7

J, 53 bytes

<(0{]#~a:=-.&,&.>)[:(/:#@,@>)@,<<;._3&>~],@{@;&(#\)|:

Try it online!

Answer 8

Perl 5, 193 bytes

sub f{($_,$r)=(@_,\"$_[0]");$u=sub{my%h;@h{pop=~/\S+/g}=();keys%h};&$u($_)<&$u($$r)or$$r=@{[/\S+/g]}<@{[$$r=~/\S+/g]}?$_:$$r,f($_,$r)for s/^\S+\s*//gmr,s/\s+\S+$//gmr,s/\n.*$//r,s/^.*\n//r;$$r}

Try it online!