# Find a representative submatrix

You have a matrix of size m x n.

Each cell in the matrix has a uniformly random integer value v, where 0 ≤ v < i, and i ≤ (m x n). (Meaning, the matrix contains a maximum of m x n distinct values, but it may have fewer.)

1) Write a function that accepts input values of m, n, i, and returns a matrix that meets the criteria above.

2) Write a second function that accepts the output of the first function as input, and returns the smallest contiguous submatrix that contains every value of v (by returning the submatrix itself, or its coordinates). By “smallest” I mean the submatrix containing the fewest cells.

(If it helps you visualize, the original inspiration for this problem was wondering how to find the smallest rectangle within a GIF that contained all the colors in its palette.)

• This needs some clarification about the randomness. Clearly the random variables aren't independent, because that would conflict with the requirement that every possible value of v appear at least once. So what are the permitted distributions? Oct 22, 2014 at 7:39
• @PeterTaylor: As I understand it, you could for example first place the values from 0 to *i*−1 randomly on the matrix, then fill up the remaining elements with random numbers from 0 to *i*−1. (Or anything that produces the same distribution of matrices.) Oct 22, 2014 at 10:45
• @Wrzlprmft, probably. But could you also just make all the matrices generated by your program be permutations of the first mn characters from an infinite sequence which just repeats 0 to i? Oct 22, 2014 at 11:02
• @weston When i = mn, the second part of the question is trivial, so i ≤ mn is deliberate. Oct 22, 2014 at 14:57
• Smallest submatrix regarding which metric? Product of dimensions? Oct 22, 2014 at 18:35

## APL (23 + 56 = 79)

### Function 1 (23):

{¯1+⍵⍴(V⍴⍺?⍺)[V?V←×/⍵]}


This takes i as its left argument and m n as its right argument, like so:

      +mat←8 {¯1+⍵⍴(V⍴⍺?⍺)[V?V←×/⍵]} 5 5
2 4 7 1 3
7 5 6 7 3
3 1 2 4 6
0 4 2 6 1
5 5 0 0 6


### Function 2 (56):

{⊃V[⍋≢∘∊¨V←V/⍨{∧/⍵∊⍨∪∊M}¨V←⊃,/{↓∘⍵¨¯1+,⍳⍴⍵}¨↑∘⍵¨,⍳⍴M←⍵]}


This takes the output from the first function as its right argument, like so:

      {⊃V[⍋≢∘∊¨V←V/⍨{∧/⍵∊⍨∪∊M}¨V←⊃,/{↓∘⍵¨¯1+,⍳⍴⍵}¨↑∘⍵¨,⍳⍴M←⍵]} mat
7 5 6
3 1 2
0 4 2

• This makes me want to learn APL. Oct 31, 2014 at 16:44