Aleatoriedad arbitraria

26

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?

Skidsdev
fuente
2
relacionado , pero muy diferente
Giuseppe
1
(P / S:. Si usted tiene un algoritmo rápido, pero toma más bytes, considere esperar hasta la edición de velocidad (actualmente en caja de arena) para publicarlo)
user202729
1
@EriktheOutgolfer Aunque existen formas (mucho) mejores que generar todos los conjuntos y elegir uno aleatorio, son mucho más difíciles de implementar y probablemente más largos. Guárdalos para la edición de velocidad.
usuario202729
2
El número de juegos es OEIS A107379 .
nwellnhof el
1
Son ambos. Vea el comentario "También el número de particiones de n ^ 2 en n partes distintas".
nwellnhof el

Respuestas:

9

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

ais523
fuente
La segunda fórmula es "el coeficiente de x^(n*(n-1)/2)expansión en serie de Product_{k=1..n} 1/(1 - x^k)" (desafortunadamente no es directo en absoluto)
user202729
Colocar la restricción "todos diferentes" antes del paso de etiquetado aleatorio (por ejemplo A≠≜₁ᵐ) hace que el tiempo de ejecución sea mucho más rápido en promedio.
Fatalize
No entiendo por qué hiciste esto una wiki comunitaria. Es una forma arcaica de tener publicaciones editables antes de que fuera posible editarlas.
tubería
7

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)
Kevin Cruijssen
fuente
5

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.

ngm
fuente
@Giuseppe "arreglado" :-)
ngm
muy agradable. usar pdirectamente como índice en lugar de calcularlo y volver a usarlo debería ahorrar algunos bytes.
Giuseppe
1
Tengo function(n){while(sum(F)!=n^2)F=sample(n^2,n);F}48 también ...
Giuseppe
1
@ J. Haz para evitar el problema al llamar a algo como lo sample(2,1)que sucede n=2. Así que repsolo garantiza que esto nunca sucederá. Puede haber una mejor manera, pero esto fue rápido y estaba enojado sample.
ngm
1
Puede guardar un byte con x*!!1:2over rep(x,2)si su meta pregunta obtiene un no.
J.Doe
4

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.

usuario202729
fuente
4

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)
Kevin Cruijssen
fuente
1
n=25¡En menos de 2 segundos es impresionante! Tendré que leer la explicación y ver cómo lo hace. ¿Sigue siendo un método de fuerza bruta?
Skidsdev
¿Es uniforme? -
user202729
@ user202729 Aunque no estoy seguro de cómo probarlo, creo que lo es. El Java incorporado es uniforme, y lo utiliza para obtener valores aleatorios en el rango [0, n squared)primero, y luego calcula las diferencias entre esos valores aleatorios ordenados (incluidos el inicio 0y el final n squared. Así que estoy bastante seguro de que esas diferencias también son uniformes. Pero de nuevo , No estoy seguro de cómo demostrarlo. La uniformidad en la aleatoriedad no es realmente mi experiencia tbh.
Kevin Cruijssen
3
¿Nunca lees del conjunto de diferencias do me falta algo?
nwellnhof el
1
Estoy un poco contento con mi solución de 127 bytes : D
Olivier Grégoire
4

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
Sean
fuente
40 bytes
Jo King
2

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./*

Sok
fuente
2

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.

Gigaflop
fuente
1
Entonces, ¿esto utiliza la recursividad para "regenerar" el conjunto si el generado no es válido? Definitivamente, algo está mal con su código si está alcanzando la profundidad de recursión f(1), la única matriz posible que debería ser generable n=1es que [1]también hay una gran cantidad de espacios en blanco extraños para eliminar aquí. Recuerde que este es un desafío de código de golf, por lo que el objetivo es lograr el bytecount más bajo
Skidsdev
1
range(1,n)-> range(n)Creo que debería resolver el error.
Jonathan Allan
1
Esto debería solucionar su error, y también elimina espacios en blanco extraños. Me imagino que también hay mucho más espacio para jugar al golf
Skidsdev el
1
Aunque la recursividad empeora ligeramente de 5 a 4, puede combinar sus dos declaraciones de retorno de esta manera: return len(s)==n and sum(s)==n*n and s or f(n)( Pruébelo en línea 114 bytes ).
Kevin Cruijssen
1
Puedes tenerlo todo en una línea. 111 bytes
Jo King
2

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

Adán
fuente
viste mis 18 bytes y los de H.PWiz ?
ngn
@ngn No, claramente no, pero verifiqué que no se haya publicado ninguna solución APL antes de publicar. ¿Por qué ninguno de ustedes?
Adám
bueno, una vez que lo jugué y lo mostré en el huerto, casi no hay ningún incentivo para publicar :)
ngn
@ngn Para ti, no, pero para mí sí.
Adám
1
ciertamente, y creo que estás haciendo un gran trabajo popularizando apl aquí. i estaba asegurando que sabes soluciones más cortas se han encontrado y es probablemente mejor para explicar uno de ellos (o una variante) en lugar
NGN
2

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 n2

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

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

ngn
fuente
1

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
Giuseppe
fuente
No intentaría esto en R: los caracteres aleatorios casi nunca producen un programa válido.
ngm
@ngm jajaja supongo que una explicación está en orden.
Giuseppe
1

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
Lanudo
fuente
Según un comentario hecho por el OP, el orden de los elementos en la salida es irrelevante, por lo que àdebería estar bien.
Kamil Drakari
Gracias, @KamilDrakari. Actualizado.
Shaggy
1

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.

Olivier Grégoire
fuente
Puede jugar al golf 3 bytes cambiando if(r.size()==n&s==0)a if(r.size()+s==n).
Kevin Cruijssen
@KevinCruijssen También lo he pensado, pero no, no puedo porque s podría ser -1 yn podría ser tamaño () - 1.
Olivier Grégoire
Ah, espera, sigues agregando elementos al conjunto todo el tiempo s>0, por lo que el tamaño puede ser mayor que n. Ok, en ese caso no funciona. nes una constante, pero desafortunadamente ambas sy r.size()son variables que pueden ser tanto inferiores como superiores 0y nrespectivamente.
Kevin Cruijssen
1

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.
Neil
fuente
1

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.

invitado271314
fuente
1
637 bytes tirando de z.join en una variable, yk++
Veskah
@Veskah Los dos whilebucles probablemente también podrían reducirse al cuerpo de una sola función que acepta parámetros; y podría sustituir operadores condicionales (ternarios) por las if..elsedeclaraciones; entre otras partes del código que probablemente podrían ajustarse para el golf; ieg, eliminando letdeclaraciones.
invitado271314
@Veskah 601 bytes sin sustituir ternaria paraif..else
guest271314
1
Ah, sí, estás sacando todos los sets mientras que el desafío pide que se devuelva uno al azar (ver los comentarios del OP para más detalles)
Veskah
@Veskah Debe haber malinterpretado el desafío y los ejemplos, o estaba demasiado concentrado en resolver esta parte de la pregunta " Tarea adicional: ¿hay una fórmula para calcular el número de permutaciones válidas para un determinado n?" . probando resultado esperado si el algoritmo devuelve constantemente para n^2arrays de salida generadas en una sola llamada a la función, y considerando simultáneamente las similitudes a esta pregunta N N-dimensional ^ array N lleno de N .
invitado271314
0

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
Kamil Drakari
fuente
0

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

y+(y+1)+(y+2)+...
x
k(k+1)2+k(y+1)+y<X

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.

LambdaBeta
fuente
Me encantaría que alguien revisara mis matemáticas en busca de consistencia. También me pregunto si este tipo de solución podría hacer que el desafío uniforme de velocidad aleatoria sea simple. La fórmula coloca un límite superior e inferior en la respuesta, ¿un número aleatorio uniforme en ese rango da como resultado resultados aleatorios uniformes? No veo por qué no, pero no he hecho mucha combinatoria en un tiempo.
LambdaBeta
Sugerir en p(y),x-=y++)while(rand()&&(i-n)*((~n+i)/2+~y)+y<x)y++;lugar de){while(rand()&&(n-i)*(n-i+1)/2+(n-i)*(y+1)+y<x)y++;p(y);x-=y++;}
ceilingcat
@ceilingcat Me encantan estas pequeñas mejoras que encuentras. Siempre me concentro tanto en el algoritmo general que olvido optimizar para la implementación (básicamente uso el modo de golf de piloto automático una vez que tengo una fuente que no es de golf que funciona, por lo que pierdo muchos ahorros)
LambdaBeta
Oye, no eres solo tú quien tiene esos campos de sintaxis. Encuentro pequeñas mejoras en muchas respuestas C / C ++ como esa (excepto que no en la suya, @ceilingcat generalmente las ajusta).
Zacharý
Sí, he notado que ustedes dos son probablemente los putters C / C ++ más activos (¿podemos usar el put para extender la analogía del golf a los últimos golpes? ¿Por qué no?). Siempre me impresiona que incluso puedas entender el código de golf lo suficientemente bien como para mejorarlo.
LambdaBeta
0

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!

Οurous
fuente
0

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)

ArBo
fuente
0

Mathematica 40 bytes

RandomChoice[IntegerPartitions[n^2, {n}]]
David G. Stork
fuente
1
Primero que nada es n ^ 2, no 2 ^ n. En segundo lugar, su programa debe ser una función y también de golf. Prueba esto RandomChoice@IntegerPartitions[#^2,{#}]&
J42161217
1
Además, el resultado debe ser (desordenado, único) pero esta función falla en ambos
J42161217
0

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

norte2nortenorte2-(norte2-norte)/ /2=(norte2+norte)/ /20 0norte-1norte-10 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?

pagsunart(norte,k)nortek

pagsunart(norte,k)=pagsunart(norte-1,k-1)+pagsunart(norte-k,k)

pagsunart(norte,1)=1norte<kpagsunart(norte,k)=0 0

pagsunart(norte2+norte2,norte)

que es, en Mathematica:

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

Pruébalo en línea!

Bubbler
fuente
Este es el código de golf ... 49 bytes(While[Tr[s=RandomSample[Range[#^2],#]]!=#^2];s)&
J42161217