La aleatoriedad es divertida. Los desafíos sin sentido son divertidos.

Escriba una función que, dada la entrada de enteros n, generará un conjunto (desordenado, único) de nenteros exactamente aleatorios entre 1e n^2(inclusive) de modo que la suma de todos los enteros sea igual a n^2.

La aleatoriedad no tiene que ser uniforme, siempre que cada conjunto válido tenga una probabilidad distinta de cero.

La respuesta más corta en bytes (por cada idioma) gana.

Ejemplos

Input (n) = 1, Target (n^2) = 1
Sample of possible outputs:
1

Input = 2, Target = 4
Sample of possible outputs:
3, 1
1, 3

Input = 3, Target = 9
Sample of possible outputs:
6, 1, 2
3, 5, 1
4, 3, 2

Input = 4, Target = 16
Sample of possible outputs:
1, 3, 5, 7
2, 4, 1, 9
8, 3, 1, 4

Input = 5, Target = 25
Sample of possible outputs:
11, 4, 7, 1, 2
2, 3, 1, 11, 8
6, 1, 3, 7, 8

Input = 8, Target = 64
Sample of possible outputs:
10, 3, 9, 7, 6, 19, 8, 2
7, 16, 2, 3, 9, 4, 13, 10
7, 9, 21, 2, 5, 13, 6, 1

Tarea adicional: ¿hay una fórmula para calcular el número de permutaciones válidas para un determinado n?

Brachylog (v2), 15 bytes (aleatorio) o 13 bytes (todas las posibilidades)

Aleatorio

~lℕ₁ᵐA+√?∧A≜₁ᵐ≠

Pruébalo en línea!

Envío de funciones (visto en TIO con un contenedor que lo convierte en un programa completo).

Explicación

~lℕ₁ᵐA+√?∧A≜₁ᵐ≠
~l               Specify a property of a list: its length is equal to the input,
    ᵐ              and it is composed entirely of
  ℕ₁                 integers ≥ 1,
       √           for which the square root of the
      +              sum of the list
        ?              is the input.
     A   ∧A      Restricting yourself to lists with that property,
           ≜₁      pick random possible values
             ᵐ       for each element in turn,
              ≠    until you find one whose elements are all distinct.

Todas las posibilidades

~lℕ₁ᵐ<₁.+√?∧≜

Pruébalo en línea!

Envío de funciones, que genera todas las salidas posibles.

Explicación

~lℕ₁ᵐ<₁.+√?∧≜
~l               Specify a property of a list: its length is equal to the input,
    ᵐ              it is composed entirely of
  ℕ₁                 integers ≥ 1,
     <₁            it is strictly increasing,
         √         and the square root of the
        +            sum of the list
          ?            is the input.
       .   ∧≜    Generate all specific lists with that property.

Estoy bastante sorprendido de que ∧≜funcione (normalmente tendrías que escribir ∧~≜para forzar la salida en lugar de la entrada), pero resulta que ≜tiene un supuesto de entrada = salida, por lo que no importa en qué dirección ejecutarlo.

Tarea de bonificación

Para obtener una idea de la secuencia del número de posibilidades, creé un contenedor TIO diferente que ejecuta el programa en enteros sucesivos para dar la secuencia de conteos de salida:

1,1,3,9,30,110,436,1801,7657,33401

Un viaje a OEIS descubre que esta es una secuencia conocida, A107379 , descrita más o menos como en la pregunta (al parecer, obtiene la misma secuencia si la restringe a números impares). La página enumera varias fórmulas para la secuencia (aunque ninguna es particularmente simple; la segunda parece una fórmula directa para el valor pero no entiendo la notación).

05AB1E , 11 bytes

nÅœʒDÙQ}sùΩ

Pruébelo en línea o verifique todos los casos de prueba .

Explicación:

n             # Take the square of the (implicit) input
              #  i.e. 3 → 9
 Ŝ           # Get all integer-lists using integers in the range [1, val) that sum to val
              #  i.e. 9 → [[1,1,1,1,1,1,1,1,1],...,[1,3,5],...,[9]]
   ʒ   }      # Filter the list to only keep lists with unique values:
    D         # Duplicate the current value
     Ù        # Uniquify it
              #  i.e. [2,2,5] → [2,5]
      Q       # Check if it's still the same
              #  i.e. [2,2,5] and [2,5] → 0 (falsey)
        s     # Swap to take the (implicit) input again
         ù    # Only leave lists of that size
              #  i.e. [[1,2,6],[1,3,5],[1,8],[2,3,4],[2,7],[3,6],[4,5],[9]] and 3
              #   → [[1,2,6],[1,3,5],[2,3,4]]
          Ω   # Pick a random list from the list of lists (and output implicitly)

Python (2 o 3), 85 bytes

def f(n):r=sample(range(1,n*n+1),n);return(n*n==sum(r))*r or f(n)
from random import*

Pruébalo en línea!

R , 68, 75 48 bytes (aleatorio) y 70 bytes (determinista)

Método de muestreo de rechazo de @ Giuseppe:

function(n){while(sum(F)!=n^2)F=sample(n^2,n);F}

Pruébalo en línea!

Golfed original:

function(n,m=combn(1:n^2,n))m[,sample(which(colSums(m)==n^2)*!!1:2,1)]

Pruébalo en línea!

El *!!1:2negocio es evitar la forma extraña de sampleactuar cuando el primer argumento tiene longitud 1.

Jalea , 9 bytes

²œcS=¥Ƈ²X

Pruébalo en línea!

Genere todas las combinaciones n de la lista [1..n²], filtre para mantener aquellas con suma n², luego elija una aleatoria.

Java 10, 250 242 222 bytes

import java.util.*;n->{for(;;){int i=n+1,r[]=new int[i],d[]=new int[n];for(r[n<2?0:1]=n*n;i-->2;r[i]=(int)(Math.random()*n*n));var S=new HashSet();for(Arrays.sort(r),i=n;i-->0;)S.add(d[i]=r[i+1]-r[i]);if(!S.contains(0)&S.size()==n)return S;}}

-20 bytes gracias a @nwellnhof .

Cuidado, Java viene ... Es 'solo' cinco veces más que las otras cuatro respuestas combinadas, así que no está mal, supongo ... rofl.
Que se ejecuta n=1a través de n=25(combinado) en menos de 2 segundos sin embargo, así que probablemente publicar una versión modificada de la versión de la velocidad de este desafío (que es actualmente todavía en la zona de pruebas) también.

Pruébalo en línea.

Explicación:

En pseudocódigo hacemos lo siguiente:

1) Generar una matriz de tamaño n+1que contiene: 0, ncuadrado, y n-1cantidad de números enteros aleatorios en el rango de [0, n squared)
2) Ordenar esta matriz
3) Crear una segunda matriz de tamaño nque contiene las diferencias hacia adelante de pares
Estos tres primeros pasos nos darán una matriz que contiene nal azar enteros (en el rango [0, n squared)que suma al ncuadrado.
4a) Si no todos los valores aleatorios son únicos, o alguno de ellos es 0: intente nuevamente desde el paso 1
4b) De lo contrario: devuelva esta matriz de diferencias como resultado

En cuanto al código real:

import java.util.*;      // Required import for HashSet and Arrays
n->{                     // Method with int parameter and Set return-type
  for(;;){               //  Loop indefinitely
    int i=n+1,           //   Set `i` to `n+1`
        r[]=new int[i];  //   Create an array of size `n+1`
    var S=new HashSet(); //   Result-set, starting empty
    for(r[n<2?           //   If `n` is 1:
           0             //    Set the first item in the first array to:
          :              //   Else:
           1]            //    Set the second item in the first array to:
             =n*n;       //   `n` squared
        i-->2;)          //   Loop `i` in the range [`n`, 2]:
      r[i]=              //    Set the `i`'th value in the first array to:
           (int)(Math.random()*n*n); 
                         //     A random value in the range [0, `n` squared)
    for(Arrays.sort(r),  //   Sort the first array
        i=n;i-->0;)      //   Loop `i` in the range (`n`, 0]:
      S.add(             //    Add to the Set:
        r[i+1]-r[i]);    //     The `i+1`'th and `i`'th difference of the first array
    if(!S.contains(0)    //   If the Set does not contain a 0
       &S.size()==n)     //   and its size is equal to `n`:
      return S;}}        //    Return this Set as the result
                         //   (Implicit else: continue the infinite loop)

Perl 6 , 41 bytes

{first *.sum==$_²,(1..$_²).pick($_)xx*}

Pruébalo en línea!

• (1 .. $_²) es el rango de números del 1 al cuadrado del número de entrada
• .pick($_) elige aleatoriamente un subconjunto distinto de ese rango
• xx * replica la expresión anterior infinitamente
• first *.sum == $_² selecciona el primero de esos conjuntos de números que suman al cuadrado del número de entrada

Pyth, 13 12 bytes

Ofq*QQsT.cS*

Pruébelo en línea aquí . Tenga en cuenta que el intérprete en línea se encuentra con un MemoryError para entradas mayores de 5.

Ofq*QQsT.cS*QQQ   Implicit: Q=eval(input())
                 Trailing QQQ inferred
          S*QQQ   [1-Q*Q]
        .c    Q   All combinations of the above of length Q, without repeats
 f                Keep elements of the above, as T, where the following is truthy:
      sT            Is the sum of T...
  q                 ... equal to...
   *QQ              ... Q*Q?
O                 Choose a random element of those remaining sets, implicit print

Editar: guardado un byte adoptando un enfoque alternativo. Versión previa: Of&qQlT{IT./*

Python 3 , 136134127121114 bytes

from random import*
def f(n):
	s={randint(1,n*n)for _ in range(n)}
	return len(s)==n and sum(s)==n*n and s or f(n)

Pruébalo en línea!

Un comentarista me corrigió, y esto ahora alcanza la profundidad máxima de recursión en f (5) en lugar de f (1). Mucho más cerca de ser una respuesta competitiva real.

Lo he visto hacer f (5) una vez , y estoy trabajando en tratar de implementar esto con shuffle.

Intenté hacer algunas expresiones lambda para s=..., pero eso no ayudó en bytes. Quizás alguien más pueda hacer algo con esto: s=(lambda n:{randint(1,n*n)for _ in range(n)})(n)

Gracias a Kevin por eliminar otros 7 bytes.

APL (Dyalog Unicode) , ^{SBCS de} 20 bytes

Prefijo anónimo lambda.

{s=+/c←⍵?s←⍵*2:c⋄∇⍵}

Pruébalo en línea!

{... } "dfn"; ⍵es argumento

 ⍵*2 cuadrar el argumento

 s← asignar a s(para s quare)

 ⍵? encuentre níndices aleatorios de 1 ... ssin reemplazo

 c← asignar a c(para c andidate)

 +/ sumalos

 s= comparar con s

 : si es igual

  c devolver al candidato

 ⋄ más

  ∇⍵ recurse en el argumento

APL (Dyalog Classic) , 18 bytes

(≢?≢×≢)⍣(0=+.-∘≢)⍳

Pruébalo en línea!

usos ⎕io←1

⍳ genera los números 1 2 ... n

(... )⍣(... )siga aplicando la función de la izquierda hasta que la función de la derecha devuelva verdadero

≢ longitud, es decir n

≢?≢×≢elija nenteros al azar distintos entre 1 y n²

+.-∘≢ reste la longitud de cada número y suma

0= si la suma es 0, deje de repetir, de lo contrario intente nuevamente

MATL , 18 13 bytes

`xGU:GZrtsGU-

Pruébalo en línea!

`	# do..while:
x	# delete from stack. This implicitly reads input the first time
	# and removes it. It also deletes the previous invalid answer.
GU:	# paste input and push [1...n^2]
GZr	# select a single combination of n elements from [1..n^2]
tsGU-	# is the sum equal to N^2? if yes, terminate and print results, else goto top

Japt, 12 bytes

²õ àU ö@²¥Xx

Intentalo

                 :Implicit input of integer U
²                :U squared
 õ               :Range [1,U²]
   àU            :Combinations of length U
      ö@         :Return a random element that returns true when passed through the following function as X
        ²        :  U squared
         ¥       :  Equals
          Xx     :  X reduced by addition

Java (JDK) , 127 bytes

n->{for(int s;;){var r=new java.util.TreeSet();for(s=n*n;s>0;)r.add(s-(s-=Math.random()*n*n+1));if(r.size()==n&s==0)return r;}}

Pruébalo en línea!

Bucle infinito hasta que coincida un conjunto con los criterios.

Espero que tengas tiempo, ¡porque es muy lento! Ni siquiera puede llegar a 10 sin tiempo de espera.

Lote, 182 145 bytes

@set/an=%1,r=n*n,l=r+1
@for /l %%i in (%1,-1,1)do @set/at=n*(n-=1)/2,m=(r+t+n)/-~n,r-=l=m+%random%%%((l-=x=r+1-t)*(l^>^>31)+x-m)&call echo %%l%%

Explicación: Calcula la selección mínima y máxima permitida, dado que los números deben seleccionarse en orden descendente, y elige un valor aleatorio dentro del rango. Ejemplo para una entrada de4 :

• Comenzamos con 16 restantes. No podemos elegir 11 o más porque las 3 selecciones restantes deben agregar al menos a 6. También necesitamos elegir al menos 6, porque si solo elegimos 5, las 3 selecciones restantes solo pueden agregar a 9, lo cual no es suficiente para 16. Elegimos un valor aleatorio de 6 a 10, digamos 6.
• Nos quedan 10. No podemos elegir 8 o más porque las 2 selecciones restantes deben sumar al menos 3. Como sucede, no podemos elegir 6 o más porque elegimos 6 la última vez. También necesitamos elegir al menos 5, porque si solo elegimos 4, las 2 selecciones restantes solo pueden sumar 5, para un total de 15. Elegimos un valor aleatorio de 5 a 5, digamos 5 (!).
• Nos quedan 5. No podemos elegir 5 o más porque la selección restante debe agregarse al menos a 1, y también porque elegimos 5 la última vez. También necesitamos elegir al menos 3, porque si solo elegimos 2, la selección restante solo puede ser 1, para un total de 14. Elegimos un valor aleatorio de 3 a 4, digamos 4.
• Nos queda 1. Como resultado, el algoritmo elige un rango de 1 a 1, y elegimos 1 como el número final.

JavaScript, 647 291 261 260 259 251 239 bytes

Gracias a @Veskah por -10 bytes en la versión original y "Oh sí, estás enviando todos los conjuntos mientras que el desafío pide que se devuelva uno aleatorio"

(n,g=m=n**2,r=[...Array(g||1)].map(_=>m--).sort(_=>.5-Math.random()).slice(-n),c=_=>eval(r.join`+`),i=_=>r.includes(_))=>[...{*0(){while(g>1&&c()!=g){for(z of r){y=c();r[m++%n]=y>g&&!(!(z-1)||i(z-1))?z-1:y<g&&!i(z+1)?z+1:z}}yield*r}}[0]()]

Pruébalo en línea!

Cree una matriz de n^2índices basados ​​en 1, ordene la matriz al azar, corte nelementos de la matriz. Mientras que la suma de los elementos aleatorios no es igual a la n^2matriz de bucle de elementos aleatorios; si la suma de los elementos de la matriz es mayor que el n^2elemento actual-1 no es igual a cero o el elemento actual -1no está en la matriz actual, reste 1; si la suma de la matriz es menor que n^2y el elemento actual +1no está en la matriz, agregue 1al elemento. Si la suma de la matriz es igual a n^2romper el bucle, la matriz de salida.

Japt , 20 bytes

²õ ö¬oU íUõ+)Õæ@²¥Xx

Pruébalo en línea!

Aprovecha en gran medida la aleatoriedad "no uniforme", casi siempre genera los primeros nnúmeros impares, que suman n^2. En teoría, puede generar cualquier otro conjunto válido, aunque solo he podido confirmarlo por pequeño n.

Explicación:

²õ                      :Generate the range [1...n^2]
   ö¬                   :Order it randomly
     oU                 :Get the last n items
        í   )Õ          :Put it in an array with...
         Uõ+            : The first n odd numbers
              æ_        :Get the first one where...
                  Xx    : The sum
                ²¥      : equals n^2

Ruby , 46 bytes

->n{z=0until(z=[*1..n*n].sample n).sum==n*n;z}

Pruébalo en línea!

C (gcc) , 128 125 bytes

p(_){printf("%d ",_);}f(n,x,y,i){x=n*n;y=1;for(i=0;++i<n;p(y),x-=y++)while(rand()&&(n-i)*(n-i+1)/2+(n-i)*(y+1)+y<x)y++;p(x);}

Pruébalo en línea!

-3 bytes gracias a ceilingcat

NOTA: La probabilidad está muy muy lejos de ser uniforme. Vea la explicación de lo que quiero decir y un mejor medio para probar que funciona (haciendo que la distribución sea más cercana al uniforme [pero aún muy lejos de eso]).

¿Cómo?

La idea básica es elegir solo números crecientes para no preocuparse por los duplicados. Cada vez que elegimos un número, tenemos una probabilidad distinta de cero de 'omitirlo' si es posible.

xky

No obstante, la lógica es tener la oportunidad de descartar cualquiera yque satisfaga la ecuación anterior.

El código

p(_){printf("%d ",_);}  // Define print(int)
f(n,x,y,i){             // Define f(n,...) as the function we want
    x=n*n;              // Set x to n^2
    y=1;                // Set y to 1
    for(i=0;++i<n;){    // n-1 times do...
        while(rand()&&  // While rand() is non-zero [very very likely] AND
            (n-i)*      // (n-i) is the 'k' in the formula
            (n-i+1)/2+  // This first half takes care of the increment
            (n-i)*(y+1) // This second half takes care of the y+1 starting point
            +y<x)       // The +y takes care of the current value of y
        y++;            // If rand() returned non-zero and we can skip y, do so
    p(y);               // Print y
    x-=y++;             // Subtract y from the total and increment it
    }p(x);}             // Print what's left over.

El truco que he mencionado a una mejor prueba del código, se colocan nuevamente rand()&&con rand()%2&&de manera que hay una probabilidad de 50-50 que cualquier dado y se pasa por alto, en lugar de un 1 en la RAND_MAXposibilidad de que se utilice cualquier Y dado.

Limpio , 172 bytes

import StdEnv,Math.Random,Data.List
? ::!Int->Int
?_=code{
ccall time "I:I"
}
$n=find(\s=length s==n&&sum s==n^2)(subsequences(nub(map(inc o\e=e rem n^2)(genRandInt(?0)))))

Pruébalo en línea!

Python (2 o 3), 84 bytes

from random import*;l=lambda n,s=[]:(sum(s)==n*n)*s or l(n,sample(range(1,n*n+1),n))

Pruébalo en línea!

Golpea la profundidad máxima de recursión alrededor de l (5)

Kotlin , 32 bytes

{(1..it*it).shuffled().take(it)}

Pruébalo en línea!

Mathematica 40 bytes

RandomChoice[IntegerPartitions[n^2, {n}]]

Wolfram Language (Mathematica) , 49 bytes

(While[Tr[s=RandomSample[Range[#^2],#]]!=#^2];s)&

Pruébalo en línea!

Versión golfizada por @ J42161217.

Wolfram Language (Mathematica) , 62 bytes

Range[#-1,0,-1]+RandomChoice@IntegerPartitions[#*(#+1)/2,{#}]&

Pruébalo en línea!

Cómo funciona

$n^2$$n$$n^2 - (n^2-n)/2 = (n^2+n)/2$$0 \cdots n-1$$n-1 \cdots 0$

La respuesta a la tarea de bonificación

Tarea adicional: ¿hay una fórmula para calcular el número de permutaciones válidas para un determinado n?

$part(n,k)$$n$$k$

$part(n,1) = 1$$n < k \Rightarrow part(n,k) = 0$

que es, en Mathematica:

Length@IntegerPartitions[#*(#+1)/2,{#}]&

Pruébalo en línea!