Étant donné une liste non triée d'entiers strictement positifs uniques, triez-la de manière minimale dans une matrice 2D. La liste d'entrée est garantie d'être de longueur composite, ce qui signifie que la matrice de sortie n'est pas nécessairement carrée, mais est de taille n x mavec n,m > 1.

"Tri minimal" signifie ici ce qui suit:

• Triez la liste par ordre croissant.
• Compactez la matrice de sortie autant que possible - minimisez la somme des dimensions de la matrice (par exemple, pour 20les éléments d'entrée comme entrée, une matrice de sortie 5x4ou 4x5est requise, et non a 2x10).
• Compacter les nombres triés aussi loin que possible dans le coin supérieur gauche de la matrice, en commençant par le premier élément de la liste triée.
• Cela peut être considéré comme un tri de la liste, puis une coupe le long des anti-diagonales de la matrice, en commençant par le coin supérieur gauche.

Exemples:

Pour la 1..20sortie d' entrée est une matrice 5x4 ou 4x5 comme suit:

 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

Pour la [3, 5, 12, 9, 6, 11]sortie d' entrée est un 2x3 ou 3x2 comme suit

3  5  9
6 11 12

 3  5
 6  9
11 12

Pour l'entrée [14, 20, 200, 33, 12, 1, 7, 99, 58], la sortie est un 3x3 comme suit

 1   7  14
12  20  58
33  99 200

Pour l'entrée, 1..10la sortie doit être un 2x5 ou 5x2 comme suit

1 2 4 6  8
3 5 7 9 10

1  2
3  4
5  6
7  8
9 10

Pour la [5, 9, 33, 65, 12, 7, 80, 42, 48, 30, 11, 57, 69, 92, 91]sortie d' entrée est un 5x3 ou 3x5 comme suit

 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

Règles

• L'entrée peut être supposée correspondre au type d'entier natif de votre langue.
• L'entrée et la sortie peuvent être fournies par n'importe quelle méthode pratique .
• Un programme complet ou une fonction sont acceptables. S'il s'agit d'une fonction, vous pouvez renvoyer la sortie plutôt que de l'imprimer.
• Les failles standard sont interdites.
• Il s'agit de code-golf, donc toutes les règles de golf habituelles s'appliquent et le code le plus court (en octets) l'emporte.

Gelée , 24 22 20 octets

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

Essayez-le en ligne!

Enregistré 2 octets grâce à @ Jonathan Allan .

Explication

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)

Python 2 , 160 158 153 151 octets

^{-2 octets grâce à Erik l'Outgolfer
-2 octets merci à M. 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

Essayez-le en ligne! ou Essayez tous les cas de test

R 110 95 octets

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)}

Essayez-le en ligne!

Comment ça fonctionne

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 a sauvé un énorme 15 (!) Octets par les astuces suivantes

• remplacement length(x)par sum(x|1)(-1 octet)
• floor()n'est pas requis car l' :arrondi de toute façon (-7)
• ^.5est plus court que sqrt()(-3)
• utiliser col(X) + row(X)au lieu de outer(sympa!)
• ne pouvait pas se débarrasser de la t(X)- décevant;)

Solution originale

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)}

Il semblerait plus sophistiqué d' outerêtre remplacé par row(X)+col(X), mais cela nécessiterait d'initialiser la matrice de sortie en Xpremier.

Essayez-le en ligne!

JavaScript (ES6), 172 octets

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)

Explication

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

Cas de test

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]))

Perl 5 , 132 octets

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}

Essayez-le en ligne!

La sous-routine renvoie un tableau 2D. Le lien TIO comprend un code de pied de page pour afficher le résultat du test.

Octave , 151 octets

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

Utilisation de trois types différents de constructions de boucles.

Essayez-le en ligne!

Déroulé:

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

Husk , 15 octets

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

Cela fonctionne par force brute, donc les cas de test plus longs peuvent expirer. Essayez-le en ligne!

Explication

ḟȯΛ≤Σ∂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).

C (gcc) , 269 octets

j,w,h,x,y;f(A,l)int*A;{int B[l];for(w=l;w-->1;)for(j=0;j<w;)if(A[j++]>A[j]){h=A[~-j];A[~-j]=A[j];A[j]=h;}for(w=h=j=2;w*h-l;j++)l%j||(w=h,h=j),h*h-l||(w=j);for(x=0;x<w*h;x++)for(y=0;y<=x;y++)x-y<w&y<h&&(B[x-y+y*w]=*A++);for(j=0;j<l;j++)j%w||puts(""),printf("%d ",B[j]);}

Essayez-le en ligne!

JavaScript (ES6), 233 octets

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,[])}

Explication

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
      ,[]
     )
}

Java 10, 199 188 186 octets

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;}

Essayez-le en ligne.

Basé sur ma réponse ici .

Explication:

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