Minimally sort a list into a matrix

Question

Given an unsorted list of unique strictly positive integers, minimally sort it into a 2D matrix. The input list is guaranteed to be of composite length, which means the output matrix is not necessarily square, but is of size n x m with n,m > 1.

"Minimally sort" here means the following:

Sort the list in ascending order.
Compact the output matrix as much as possible -- minimize the sum of the dimensions of the matrix (for example, for 20 input elements as input, a 5x4 or 4x5 output matrix is required, and not a 2x10).
Compact the sorted numbers as far to the upper-left of the matrix as possible, starting with the first element in the sorted list.
This can be thought of as sorting the list, then slicing it along the matrix's anti-diagonals, starting with the upper-left.

Examples:

For input 1..20 output is either a 5x4 or a 4x5 matrix as follows:

 1  2  4  7 11
 3  5  8 12 15
 6  9 13 16 18
10 14 17 19 20

 1  2  4  7
 3  5  8 11
 6  9 12 15
10 13 16 18
14 17 19 20

For input [3, 5, 12, 9, 6, 11] output is a 2x3 or 3x2 as follows

For input [14, 20, 200, 33, 12, 1, 7, 99, 58], output is a 3x3 as follows

 1   7  14
12  20  58
33  99 200

For input 1..10 the output should be a 2x5 or 5x2 as follows

For input [5, 9, 33, 65, 12, 7, 80, 42, 48, 30, 11, 57, 69, 92, 91] output is a 5x3 or 3x5 as follows

 5  7 11 33 57
 9 12 42 65 80
30 48 69 91 92

 5  7 11
 9 12 33
30 42 57
48 65 80
69 91 92

Rules

The input can be assumed to fit in your language's native integer type.
The input and output can be given by any convenient method.
Either a full program or a function are acceptable. If a function, you can return the output rather than printing it.
Standard loopholes are forbidden.
This is code-golf so all usual golfing rules apply, and the shortest code (in bytes) wins.

Oh, wow, a word I haven't seen since Linear Algebra; easily overlooked. My apologies. — Magic Octopus Urn, Feb 16, 2018 at 17:37

miles · Accepted Answer · 2018-02-16 19:33:24Z

Jelly, 24 22 20 bytes

pS€ỤỤs
LÆDżṚ$SÞḢç/ịṢ

Try it online!

Saved 2 bytes thanks to @Jonathan Allan.

Explanation

pS€ỤỤs  Helper link. Input: integer a (LHS), integer b (RHS)
p       Cartesian product between [1, 2, ..., a] and [1, 2, ..., b]
 S€     Sum each pair
   Ụ    Grade up
    Ụ   Grade up again (Obtains the rank)
     s  Split into slices of length b

LÆDżṚ$SÞḢç/ịṢ  Main link. Input: list A
L              Length
 ÆD            Divisors
     $         Monadic pair
    Ṛ            Reverse
   ż             Interleave
                 Now contains all pairs [a, b] where a*b = len(A)
      SÞ       Sort by sum
        Ḣ      Head (Select the pair with smallest sum)
         ç/    Call helper link
            Ṣ  Sort A
           ị   Index into sorted(A)

\$\begingroup\$ L%J¬TżṚ$ -> LÆDżṚ$ should save two I think \$\endgroup\$
– Jonathan Allan
Feb 16, 2018 at 19:18 — Jonathan Allan, Feb 16, 2018 at 19:18
\$\begingroup\$ The first link can become pSÞỤs. \$\endgroup\$
– Dennis
Apr 24, 2018 at 16:42 — Dennis, Apr 24, 2018 at 16:42

Rod · Accepted Answer · 2018-02-16 20:09:25Z

4

Python 2, 160 158 153 151 bytes

^{-2 bytes thanks to Erik the Outgolfer}
^{-2 bytes thanks to Mr. Xcoder}

s=sorted(input())
l=len(s)
x=int(l**.5)
while l%x:x+=1
n=1
o=eval(`l/x*[[]]`)
while s:
 for i in range(l/x)[max(0,n-x):n]:o[i]+=s.pop(0),
 n+=1
print o

Try it online! or Try all test cases

edited Feb 16, 2018 at 20:09

answered Feb 16, 2018 at 16:54

Rod

18.4k4 gold badges30 silver badges89 bronze badges

\$\begingroup\$ I belive you can use max(0,n-x) for -2 bytes. \$\endgroup\$
– Mr. Xcoder
Feb 16, 2018 at 17:32

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

R 110 95 bytes

function(x){n=sum(x|1)
X=matrix(x,max(which(!n%%1:n^.5)))
X[order(col(X)+row(X))]=sort(x)
t(X)}

Try it online!

How it works

f <- function(x) {
  n <- sum(x|1)                           # length
  p <- max(which(!n%%1:n^.5))             # height of matrix
  X <- matrix(x, p)                       # initialize matrix
  X[order(col(X) + row(X))] <- sort(x)    # filling the matrix using position distance to the top left corner
  t(X)                                    # probably required by OP
}

Giuseppe saved a whopping 15(!) bytes by the following tricks

replacing length(x) by sum(x|1) (-1 byte)
floor() is not required as : rounds down anyway (-7)
^.5 is shorter than sqrt() (-3)
using col(X) + row(X) instead of outer (nice!)
could not get rid of the t(X) though - disappointing ;)

Original solution

function(x){
n=length(x)
p=max(which(!n%%1:floor(sqrt(n))))
X=outer(1:p,1:(n/p),`+`)
X[order(X)]=sort(x)
t(X)}

It would look more fancy with outer being replaced by row(X)+col(X), but that would require to initialize the output matrix X first.

Try it online!

Might be able to use something from my solution to a related challenge to help here as well. — Giuseppe, Apr 25, 2018 at 11:29

Endenite · Accepted Answer · 2018-02-16 18:07:19Z

JavaScript (ES6), 172 bytes

l=>(n=l.sort((a,b)=>b-a).length,w=l.findIndex((_,i)=>!(i*i<n|n%i)),a=l=>[...Array(l)],r=a(n/w).map(_=>a(w)),a(w+n/w).map((_,x)=>r.map((s,y)=>x-y in s&&(s[x-y]=l.pop()))),r)

Explanation

l=>(                                // Take a list l as input
 l.sort((a,b)=>b-a),                // Sort it
 n=l.length,                        // Get the length n
 w=l.findIndex((_,i)=>!(i*i<n|n%i)),// Find the first integer w where w >= √n and n % w = 0
 a=l=>[...Array(l)],                // Helper function a
 r=a(n/w).map(_=>a(w)),             // Create the grid r of size w, n/w
 a(w+n/w).map((_,x)=>               // For every x from 0 to w + n/w:
  r.map((s,y)=>                     //  For every row s in r:
   x-y in s&&(                      //   If the index x-y is in s:
    s[x-y]=l.pop()))),              //    Set s[x-y] to the next element of l
 r)                                 // Return r

Test Cases

f=l=>(n=l.sort((a,b)=>b-a).length,w=l.findIndex((_,i)=>!(i*i<n|n%i)),a=l=>[...Array(l)],r=a(n/w).map(_=>a(w)),a(w+n/w).map((_,x)=>r.map((s,y)=>x-y in s&&(s[x-y]=l.pop()))),r)

l=m=>console.log(JSON.stringify(m))

l(f([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]))
l(f([3,5,12,9,6,11]))
l(f([14,20,200,33,12,1,7,99,58]))
l(f([1,2,3,4,5,6,7,8,9,10]))

Xcali · Accepted Answer · 2018-02-16 19:51:15Z

3

Perl 5, 132 bytes

sub d{$,=0|sqrt(@_=sort{$a-$b}@_);--$,while@_%$,;map{$r++,$c--for@_/$,..$c;$a[$r++][$c--]=$_;$c=++$i,$r=0if$r<0||$c<0||$r>=$,}@_;@a}

Try it online!

Subroutine returns a 2-D array. TIO link includes footer code for displaying test result.

answered Feb 16, 2018 at 19:51

Xcali

13.4k2 gold badges14 silver badges37 bronze badges

Add a comment |

Steadybox · Accepted Answer · 2018-02-18 13:07:03Z

3

Octave, 151 bytes

function f(v)n=floor(sqrt(l=nnz(v)));while i=mod(l,n);++n;end;A=nan(m=l/n,n);for k=[1:m 2*m:m:l];do A(k)=sort(v)(++i);until~mod(k+=m-1,m)|k>l;end;A'end

Using three different kinds of loop constructs.

Try it online!

Unrolled:

function f(v)
    n = floor(sqrt(l=nnz(v)));

    while i = mod(l,n);
        ++n;
    end;

    A = nan(m=l/n, n);

    for k = [1:m 2*m:m:l];
        do
            A(k) = sort(v)(++i);
        until ~mod(k+=m-1, m) | k>l;
    end;

    A'
end

edited Feb 18, 2018 at 13:07

answered Feb 16, 2018 at 17:45

Steadybox

16.5k5 gold badges40 silver badges84 bronze badges

\$\begingroup\$ Nice answer! Why is the ' in nnz(v') required? \$\endgroup\$
– Luis Mendo
Feb 18, 2018 at 4:34
1

\$\begingroup\$ @LuisMendo Thanks! Turns out the ' is not required if I wrap the range expression, e.g. 1:20, around brackets ([1:20]) at the call site (to make it an actual vector). Apparently in Octave, the colon operator doesn't create a vector, but a range constant that takes much less space in memory. For some reason, nnz() doesn't work with that type, but transposing the range constant yields a vector, so it works with the apostrophe. Calling the function with an actual vector removes the need for the '. \$\endgroup\$
– Steadybox
Feb 18, 2018 at 13:06
1

\$\begingroup\$ Thanks for the explanation. I didn't know that a range expression had that special treatment in Octave. Anyway, the fact that it doesn't create a vector for memory efficiency should be transparent to the programmer. That is, the fact that nnz(1:20) doesn't work is probably a bug (max(1:20), sum(1:20) etc are valid). \$\endgroup\$
– Luis Mendo
Feb 18, 2018 at 16:38
1

\$\begingroup\$ We should report it. It might affect other functions than nnz . Do you want to do it yourself, or shall I? \$\endgroup\$
– Luis Mendo
Feb 18, 2018 at 18:06
1

\$\begingroup\$ Reported. It also affected MATL; now solved. Thanks for noticing this! \$\endgroup\$
– Luis Mendo
Feb 18, 2018 at 18:44

| Show 2 more comments

Zgarb · Accepted Answer · 2018-02-17 09:39:27Z

Husk, 15 bytes

ḟȯΛ≤Σ∂MCP¹→←½ḊL

This works by brute force, so longer test cases may time out. Try it online!

Explanation

ḟȯΛ≤Σ∂MCP¹→←½ḊL  Implicit input, a list of integers x.
              L  Length of x (call it n).
             Ḋ   List of divisors.
            ½    Split at the middle.
          →←     Take last element of first part.
                 This is a divisor d that minimizes d + n/d.
        P¹       List of permutations of x.
      MC         Cut each into slices of length d.
ḟ                Find the first of these matrices that satisfies this:
     ∂            Take anti-diagonals,
    Σ             flatten them,
 ȯΛ≤              check that the result is sorted (each adjacent pair is non-decreasing).

Steadybox · Accepted Answer · 2018-02-17 23:51:17Z

JavaScript (ES6), 233 bytes

f=s=>{l=s.length;i=Math.sqrt(l)|0;for(;l%++i;);p=(x)=>(x/i|0+x%i)*l+x%i;m=[...Array(l).keys()].sort((x,y)=>p(x)-p(y));return s.sort((a,b)=>a-b).map((x,i)=>m.indexOf(i)).reduce((a,b,d,g)=>!(d%i)?a.concat([g.slice(d,d+i)]):a,[])}

Explanation

f=s=>{                         // Take array `s` of numbers as input
  l=s.length                   // short-hand for length
  i=Math.sqrt(l)|0             // = Math.floor(Math.sqrt(l))
  for(;l%++i;);                // i = width           
  j=l/i                        // j = height

  p=(x)=>(x/i|0+x%i)*l+x%i     // helper to calculate (sort-of) ~manhattan
                                 // distance (horizontal distance weighted
                                 // slightly stronger), from top-left corner
                                 // to the number x, if numbers 0,...,l are
                                 // arranged left-to-right, top-to-bottom
                                 // in an l=i*j grid

  m=[...Array(l).keys()]         // range array
  .sort((x,y)=>p(x)-p(y)),       // manhatten-sorted, sort-of...

  return s.sort((a,b)=>a-b)      // sort input array by numbers,
    .map((x,i,w)=>w[m.indexOf(i)])    // then apply inverse permutation of the
                                 // range-grid manhatten-sort mapping.
    .reduce(                     // slice result into rows
      (a,b,d,g)=>!(d%i)?a.concat([g.slice(d,d+i)]):a
      ,[]
     )
}

Community · Accepted Answer · 2020-06-17 09:04:33Z

Java 10, 199 188 186 bytes

a->{int j=a.length,m=0,n,i=0,k=0;for(n=m+=Math.sqrt(j);m*n<j;n=j/++m);var R=new int[m][n];for(java.util.Arrays.sort(a);i<m+n;i++)for(j=0;j<=i;j++)if(i-j<n&j<m)R[j][i-j]=a[k++];return R;}

Try it online.

Based on my answer here.

Explanation:

a->{                        // Method with int-array parameter and int-matrix return-type
  int j=a.length,           //  Length of the input-array
      m=0,n,                //  Amount of rows and columns
      i=0,k=0;              //  Index integers
   for(n=m+=Math.sqrt(j);   //  Set both `m` and `n` to floor(√ `j`)
       m*n<j;               //  Loop as long as `m` multiplied by `n` is not `j`
       n=j/++m);            //   Increase `m` by 1 first with `++m`
                            //   and then set `n` to `j` integer-divided by this new `m`
   var R=new int[m][n];     //  Result-matrix of size `m` by `n`
   for(java.util.Arrays.sort(a);
                            //  Sort the input-array
       i<m+n;)              //  Loop as long as `i` is smaller than `m+n`
     for(j=0;j<=i;j++)      //   Inner loop `j` in range [0,`i`]
       if(i-j<n&j<m)        //    If `i-j` is smaller than `n`, and `j` smaller than `m`
                            //    (So basically check if they are still within bounds)
         R[j][i-j]=a[k++];  //     Add the number of the input array at index `k`,
                            //     to the matrix in the current cell at `[j,i-j]`
  return R;}                //  Return the result-matrix

Jonathan Frech · Accepted Answer · 2020-05-26 01:33:57Z

0

C (gcc), 269 253 226 bytes

Saved 16 43 bytes thanks to ceilingcat.

j,w,h,x,y;c(int*a,int*b){a=*a-*b;}f(A,l)int*A;{int B[l];qsort(A,l,4,c);for(w=h=j=2;x=w*h-l;j++)l%j||(w=h,h=j),w=h*h-l?w:j;for(;j=x<w*h;x++)for(y=0;y<=x;y++)x-y<w&y<h?B[x-y+y*w]=*A++:0;for(;j<l;printf("\n%d "+(j++%w>0),B[j]));}

Try it online!

C (gcc), 214 bytes, using `-zexecstack`-lambdas

Thanks to ceilingcat for this hackier, yet slimmer version.

j,w,h,x,y;f(A,l)int*A;{int B[l];qsort(A,l,4,L"\x62b078bǃ");for(w=h=j=2;x=w*h-l;j++)l%j||(w=h,h=j),w=h*h-l?w:j;for(;j=x<w*h;x++)for(y=0;y<=x;y++)x-y<w&y<h?B[x-y+y*w]=*A++:0;for(;j<l;printf("\n%d "+(j++%w>0),B[j]));}

Try it online!

edited May 26, 2020 at 1:33

answered Feb 17, 2018 at 16:08

Jonathan Frech

7,3411 gold badge21 silver badges43 bronze badges

\$\begingroup\$ @ceilingcat Thank you. \$\endgroup\$
– Jonathan Frech
May 24, 2020 at 22:47
\$\begingroup\$ @ceilingcat Thank you. I assume you implemented a 'lambda' -- giving qsort a function pointer disguised as a wide-character string? Whilst I appreciate the solution, I added it as an addendum as I feel it is a tad too briddle to qualify as generic 'C'. \$\endgroup\$
– Jonathan Frech
May 26, 2020 at 0:41
\$\begingroup\$ no "lambda" 225 bytes \$\endgroup\$
– ceilingcat
May 26, 2020 at 1:31
\$\begingroup\$ @ceilingcat Thank you. \$\endgroup\$
– Jonathan Frech
May 26, 2020 at 1:34

Add a comment |

Stack Exchange Network

Minimally sort a list into a matrix

Examples:

Rules

10 Answers 10

Jelly, 24 22 20 bytes

Explanation

Python 2, 160 158 153 151 bytes

R 110 95 bytes

How it works

Original solution

JavaScript (ES6), 172 bytes

Explanation

Test Cases

Perl 5, 132 bytes

Octave, 151 bytes

Husk, 15 bytes

Explanation

JavaScript (ES6), 233 bytes

Java 10, 199 188 186 bytes

C (gcc), 269 253 226 bytes

C (gcc), 214 bytes, using `-zexecstack`-lambdas

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
array
sorting
matrix
or ask your own question.

Linked

Hot Network Questions

Minimally sort a list into a matrix

Examples:

Rules

10 Answers 10

Jelly, 24 22 20 bytes

Explanation

Python 2, 160 158 153 151 bytes

R 110 95 bytes

How it works

Original solution

JavaScript (ES6), 172 bytes

Explanation

Test Cases

Perl 5, 132 bytes

Octave, 151 bytes

Husk, 15 bytes

Explanation

JavaScript (ES6), 233 bytes

Java 10, 199 188 186 bytes

C (gcc), 269 253 226 bytes

C (gcc), 214 bytes, using -zexecstack-lambdas

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

C (gcc), 214 bytes, using `-zexecstack`-lambdas

Not the answer you're looking for? Browse other questions tagged
code-golf
array
sorting
matrix
or ask your own question.