Seleccionar aleatoriamente de una matriz

19

Este desafío es bastante simple:
se le da una matriz de enteros positivos (sin incluir 0), y tiene que seleccionar un elemento aleatorio de esta matriz.

Pero aquí está el giro:
la probabilidad de seleccionar un elemento depende del valor del entero, lo que significa que a medida que el entero se hace más grande, ¡la probabilidad de que sea seleccionado también lo hace!

Ejemplo

Te dan la matriz [4, 1, 5].

La probabilidad de seleccionar 4 es igual a 4 dividido por la suma de todos los elementos en la matriz , en este caso 4 / ( 4 + 1 + 5 ) = 4 / 10 =40%.
La probabilidad de seleccionar 1 es 1 / 10o 10%.

Entrada

Una serie de enteros positivos.

Salida

Devuelve el entero seleccionado si usa un método, o imprímalo directamente stdout.

Reglas

  • Este es el por lo que gana el código más corto en bytes en cualquier idioma.
  • Las lagunas estándar están prohibidas.
Ian H.
fuente

Respuestas:

20

Jalea , 3 bytes

x`X

Pruébalo en línea!

¡Mira, ma, no Unicode!

Explicación:

x`X
 `  Make monad from dyad and use same left and right arguments
x   Repeat each element of the left argument (implicit) list its respective number of times in the right argument list
  X Random element
Erik el Outgolfer
fuente
1
¿Puedes explicar qué hace tu código, por favor? :)
Ian H.
1
@IanH. Es realmente un algoritmo simple repetir cada elemento por sí mismo y luego elegir al azar.
Erik the Outgolfer
16

R , 25 bytes

function(s)sample(s,1,,s)

Pruébalo en línea!

Explicación:

function(s){
 sample(x = s, size = 1, replace = FALSE, prob = s)
}

Toma una muestra sde tamaño 1sin reemplazo, con pesas s; estos se reescalan para ser probabilidades.

Para verificar la distribución, use este enlace .

Giuseppe
fuente
¡Me ganaste por 9 meses! : D
JayCe
@ JayCe je, ¡mi única ventaja sobre ti parece ser "ir primero" ya que eres todo un golfista! :-)
Giuseppe
13

Pyth , 4 bytes

OsmR

Pruébalo aquí

Guardado un byte, gracias a @Jakube, con un enfoque bastante inusual.

Pyth , 5 bytes

Osm*]

Pruébalo aquí!

¿Cómo?

# 1

OsmR - Programa completo.

   R - Mapa derecho ...
  m - ... Usando el mapa. Esto esencialmente crea la lista [[4,4,4,4], [1], [5,5,5,5,5]].
       - ... ¡El crédito va a Jakube por esto!
 s - Acoplar.
O - Elemento aleatorio de ^. Mostrar implícitamente.

# 2

Osm *]: programa completo.

  m - Mapa sobre la entrada.
    ] - El elemento actual, d, envuelto; [re].
   * - Repetido d veces.
 s - Acoplar.
O - Elemento aleatorio. Imprime implícitamente el resultado.
Sr. Xcoder
fuente
1
Puedo hacerlo en 4. ¿Debería estropearlo o quieres encontrarlo tú mismo?
Jakube
2
@Jakube Espera un poquito. ¿Quieres ver si puedo hacerlo? ¿Es tan obvio?
Sr. Xcoder
1
@Jakube Ok, haré ping cuando me rinda.
Sr. Xcoder
1
OsmLoOsmR
Jakube
1
@Jakube ¡Oh, eso es muy inteligente! Argumento implícito d, luego mapas dsobre un rango ... ¡genio!
Erik the Outgolfer
8

CJam (9 bytes)

q~_]ze~mR

Demo en línea . Este es un programa completo que toma la entrada en formato de matriz CJam en stdin e imprime el elemento seleccionado en stdout.

Disección

q~   e# Read and parse input
_]z  e# Copy and transpose
e~   e# Run-length decode
mR   e# Select random element uniformly
Peter Taylor
fuente
1
Un golf tan poderoso para una tarea tan simple.
Erik the Outgolfer
7

Perl 6 , 20 bytes

Guardado 1 byte gracias a @Brad Gilbert b2gills.

{bag(@_ Zxx@_).pick}

Pruébalo en línea!

Esto toma 1 argumento de lista. Comprimimos 2 copias de esta lista utilizando el xxoperador. Entonces @_ Zxx@_, con , obtenemos una lista en la que xse presenta el elemento xveces. Luego se coacciona a Bag, que es una colección que almacena objetos junto con cuántas veces aparecen en la colección. Finalmente, elegimos un elemento aleatorio de esta colección con pick, que toma los recuentos en la cuenta y hace The Right Thing ™.

Ramillies
fuente
Esto se puede acortar a{bag(@_ Z=>@_).pick}
Brad Gilbert b2gills
@ BradGilbertb2gills, lamentablemente eso no funciona. Hace una bolsa de los pares (por lo que no habría "1" una vez, "2" dos veces, etc., sino "1 => 1" una vez, "2 => 2" también una vez, etc., no es lo que quiero) . Esto se debe a que los compositores no son coaccionadores, como se explica en este Calendario de Adviento .
Ramillies
@ BradGilbertb2gills, pero gracias de todos modos, ¡me ayudaste a jugar golf aquí y en otros desafíos también!
Ramillies
{bag(@_ Zxx@_).pick}
Quise
Aah, ya veo. Por qué no se me ocurrió ...: -) Gracias.
Ramillies
6

Python 3.6 , 44 bytes

lambda A:choices(A,A)[0]
from random import*

Yay para empotrados. El otro Aen choices(A, A)es un weightsargumento opcional .

Pruébalo en línea!

shooqie
fuente
5

MATL , 8 6 bytes

tY"1Zr

¡Pruébalo en MATL Online!

Explicación

t    % Implicit input. Duplicate
Y"   % Run-length decoding
1Zr  % Randomly take one value with uniform distribution. Implicitly display
Luis Mendo
fuente
5

Mathematica, 19 bytes

RandomChoice[#->#]&
J42161217
fuente
4

Java (OpenJDK 8) , 88 87 86 83 bytes

a->{int r=0,x=-1;for(int i:a)r-=i;for(r*=Math.random();r<1;)r+=a[++x];return a[x];}

Pruébalo en línea!

Nevay
fuente
¿Podría agregar una explicación? Estoy tratando de entender por qué for(r*=Math.random();;)se necesita, o si todo lo que necesitas es r*=Math.random().
Ayb4btu
@ Ayb4btu Sin el for(;;)bucle, esto requeriría una segunda declaración de retorno (nunca alcanzada) después for(int i:a)...de satisfacer el compilador, que sería 3 bytes más.
Nevay
Ah, por supuesto, tu for(int i:a)es como foreachen C #. Tuve el mismo problema, pero solo usé un forbucle continuo. Su nueva respuesta me intriga, podría intentar robar algunas de sus ideas.
Ayb4btu
3

J, 8 7 8 bytes

El 7 byter no es válido; Volveré a una edición anterior cuando regrese a mi computadora en un día o dos.

Pruébalo en línea!

?@+/{#~

:( seleccionar elementos aleatorios de una matriz es costoso.

8 bytes

#~{~1?+/

9 bytes

(1?+/){#~

Explicación

?@+/{#~
?        Choose random number in range
  +/     Sum of the array
    {    Select that element from
     #~  The elements duplicated as many times as their value
col
fuente
?@+/es (?@+)/; Me temo que tendrás que subir eso hasta 8 otra vez ...
FireFly
@FireFly Debería haberlo probado más, buena captura.
cole
3

JavaScript (ES6), 50 bytes

a=>a.sort((a,b)=>b-a)[Math.random()**2*a.length|0]

Esperemos que sea evidente cómo funciona esto, pero lo explicaré aquí de todos modos. Ordena los enteros en orden descendente, luego elige uno al azar con una distribución beta (1 / 2,1) .

kamoroso94
fuente
No creo que esto tenga la distribución correcta. Mis pruebas muestran que con a=[4,1,5], obtendrás aproximadamente 18% 1, 24% 4y 58% 5, lo que sugiere que obtendrás esa distribución con cualquier entrada de longitud 3.
Giuseppe
Eso me parece correcto. Mayor entero, mayor probabilidad.
kamoroso94
Oh ya veo. Leí mal la pregunta. Excelente solución, +1!
Giuseppe
2

PowerShell , 27 bytes

($args[0]|%{,$_*$_})|Random

Pruébalo en línea!

Toma la entrada $args[0]como una matriz literal. Recorre cada elemento |%{...}y cada iteración construye una nueva matriz ,$_de $_elementos, por ejemplo, para 4esto creará una matriz @(4,4,4,4). Esos elementos de la matriz se canalizan a Get-Randomcontinuación y extraerán uno de los elementos con (pseudo) probabilidad igual. Dado que, por ejemplo, @(4,1,5)esto nos da @(4,4,4,4,1,5,5,5,5,5)esto satisface los requisitos de probabilidad.

AdmBorkBork
fuente
2

C # (.NET Core) , 93 89 87 76 + 18 = 94 bytes

a=>{int i=-1,r=new Random().Next(a.Sum());while(r>=0)r-=a[++i];return a[i];}

Pruébalo en línea!

Un extra de 18 bytes para using System.Linq;

Agradecimientos

11 bytes guardados gracias a Nevay, cuya implementación de números aleatorios fue mucho más concisa (además de ser un en intlugar de undouble ).

Degolfed

a=>{
    int i=-1,
    r=new Random().Next(a.Sum());
    while(r>=0)
        r-=a[++i];
    return a[i];
}

Explicación

Obtenga un número aleatorio r, entre 0 y la suma de elementos. Luego, en cada iteración, reste el elemento actual de r. Si res menor que 0, entonces devuelva este elemento. La idea es que hay porciones más grandes del número aleatorio para los números más grandes en la matriz.

Ayb4btu
fuente
94 bytes:a=>{int i=-1,r=new Random().Next(a.Sum());for(;r>=0;)r-=a[++i];return a[i];}
Nevay
2

Japt , 7 bytes

ËÆD
c ö

Pruébalo aquí


Explicación

Entrada implícita de la matriz U.

Ë

Asigne sobre la matriz pasando cada elemento a través de una función donde Destá el elemento actual.

ÆD

Genere una matriz de longitud Dy rellénela D.

c

Aplanar.

ö

Consigue un elemento aleatorio.

Lanudo
fuente
1

Perl, 31 bytes

@a=map{($_)x$_}@ARGV;$a[rand@a]

Esto supone que la entrada son argumentos de línea de comando. Tenga en cuenta que puede quedarse sin memoria si los números son grandes.


fuente
1

Carbón de leña , 12 bytes

F⪪θ;FIι⊞υι‽υ

Pruébalo en línea! El enlace es a la versión detallada del código. Como Charcoal intenta ser demasiado inteligente, tengo que usar entradas delimitadas por punto y coma para la matriz. Explicación:

  θ             Input variable as string
 ⪪ ;            Split on semicolons
F               Loop i over each string
     Iι         Cast i to integer
    F           Repeat that many times
       ⊞υι      Push i to (originally empty) list
          ‽υ    Random selection from list
                Implicitly print
Neil
fuente
1

Javascript (ES6), 61 54 bytes

-7 bytes gracias a @Justin Mariner

a=>a.find(m=>(n-=m)<0,n=Math.random()*eval(a.join`+`))

Fragmento de código de ejemplo

f=
a=>a.find(m=>(n-=m)<0,n=Math.random()*eval(a.join`+`))
console.log(f([4,1,5]))

Herman L
fuente
Puedes sumar usando en eval(a.join`+`)lugar de reduce.
Justin Mariner
Si está de acuerdo con ES7 +, puede usar: [].find(m=>(n-=m)<0,n=Math.random()*eval(a.join+ ))y llamar coninput::[].find(...)
Downgoat
1

Haskell , 78 77 bytes

import System.Random
f l=randomRIO(0,sum l-1)>>=pure.((l>>= \n->n<$[1..n])!!)

Pruébalo en línea! Ejemplo de uso: f [1,99]probablemente rendimientos 99.

Explicación:

  • ftoma una lista de enteros ly devuelve el entero seleccionado al azar comoIO Int .
  • l>>= \n->n<$[1..n]construye una lista con cada elemento nrepetido nveces.
  • randomRIO(0,sum l-1) produce un número entero en el rango de 0 a la longitud de la lista de elementos repetidos, que es exactamente la suma de todos los elementos, menos uno para evitar una excepción fuera de límite.

Bonificación: versión sin puntos de 85 bytes

import System.Random
(>>=).randomRIO.(,)0.pred.sum<*>(pure.).(!!).(>>= \n->n<$[1..n])

Pruébalo en línea!

Laikoni
fuente
1

Java 8, 127 122 121 bytes

import java.util.*;a->{List l=new Stack();for(int i:a)for(int j=i;j-->0;Collections.shuffle(l))l.add(i);return l.get(0);}

-1 byte gracias a @Nevay .

Utiliza un enfoque similar a la respuesta Jelly de @ErikTheOutgolfer , agregando nveces el elementon a la lista, y luego selecciona uno al azar de esa lista.

Explicación:

Pruébalo aquí

import java.util.*;        // Required import for List, Stack and Collections
a->{                       // Method with integer-array parameter and integer return-type
  List l=new Stack();      //  Create a List
  for(int i:a)             //  Loop (1) over the input array
    for(int j=i;j-->0;     //   Inner loop (2) from `i` down to 0
        Collections.shuffle(l))
                           //   and shuffle the List randomly after every iteration
      l.add(i);            //    Add `i` that many times to List `l`
                           //   End of inner loop (2) (implicit / single-line body)
                           //  End of loop (1) (implicit / single-line body)
  return l.get(0);         //  And then return the first item of the list
}                          // End of method
Kevin Cruijssen
fuente
1
Puede mover la #shufflellamada al bucle for para guardar 1 byte for(int j=i;j-->0;Collections.shuffle(l))l.add(i);.
Nevay
@Nevay ¡Gracias! Reorganizar la lista después de cada iteración es bastante ineficiente, pero ¿qué nos importa sobre la eficiencia, las advertencias y demás cuando podemos deshacernos de un byte molesto adicional? ; p
Kevin Cruijssen
1

Dyalog APL , 8 bytes

/⍨⌷⍨1?+/

Pruébalo en línea!

¿Cómo?

  • /⍨, ncopias de npara cada uno nen el argumento.
  • ⌷⍨, en el índice de
  • 1?, un valor aleatorio entre 1y
  • +/, la suma del argumento
Zacharý
fuente
1

GNU APL 1.2, 26 23 bytes; 1.7 21 19 bytes

Enfoque inspirado en la respuesta de Erik the Outgolfer's Jelly . Se basa en ⎕IOser 0 en lugar de 1, que es el valor predeterminado para GNU APL (tipo de +5 bytes para ⎕IO←0).

-3, -2 bytes gracias a @ Zacharý

forma de función

∇f R
S[?⍴S←∊0 0⍉R∘.⍴R]∇

Forma anónima lambda

{S[?⍴S←∊0 0⍉⍵∘.⍴⍵]}

Para la explicación, usaré para representar el argumento pasado a la función, pero es equivalente a Ren el formulario.

⍵∘.⍴⍵calcula el producto externo en la lista utilizando el operador reshape ( ). Efectivamente, esto crea una tabla (como una tabla de multiplicación) pero en lugar de multiplicar, repite el elemento en la columna varias veces igual al elemento en la fila. Para el ejemplo dado en la pregunta, esto es:

4 4 4 4    1 1 1 1    5 5 5 5   
4          1          5         
4 4 4 4 4  1 1 1 1 1  5 5 5 5 5

0 0⍉⍵∘.⍴⍵transpone la matriz y devuelve solo la diagonal principal. Esto nos da solo las partes donde la fila y la columna ⍵∘.⍴⍵eran iguales, es decir, repetimos el número varias veces igual a su valor. Por ejemplo, esto es:

4 4 4 4  1  5 5 5 5 5

convierte su argumento en una lista. Usando el operador transpose ( ), tenemos un vector que contiene 3 vectores. Enlist ( ) lo convierte en un solo vector que contiene todos los elementos.

S←...asigna este nuevo vector a vector S. ⍴Snos da la longitud de esa lista. ?es el operador aleatorio, por lo ?⍴Sque nos da un número aleatorio entre 0 y la longitud de la lista (exclusivo) (es por eso que depende de ⎕IOser 0; de lo contrario, está entre 1 y la longitud, inclusive). S[...]devuelve el elemento en el índice dado.

Arc676
fuente
No necesitas Q, ya que nunca lo usas. Y IIRC puede eliminar la nueva línea antes del del (pequeño triángulo que marca el final de la función).
Zacharý
¡Guau, nunca fui nuevo <IO> <IO>⍉en conseguir que la diagonal principal fuera algo!
Zacharý
@ Zacharý Correcto, gracias. Francamente, ni siquiera sabía sobre la transposición hasta que intenté esta tarea tampoco. Lo encontré aquí
Arc676
Ah, existe una APL gratuita mucho mejor que GNU, se llama ngn APL. En realidad es muy bueno! ( ngn.github.io/apl/web , pero no tiene tradfn)
Zacharý
@ Zacharý También tengo esa :) lamentablemente la función de transposición no funciona (o me perdí algo). Lo probaré nuevamente ahora que tengo una mejor comprensión de cómo funciona.
Arc676
1

MATLAB, 30 bytes

@(a)datasample(repelem(n,n),1)

Esto asume MATLAB R2015a o más reciente y con la caja de herramientas Estadísticas y Aprendizaje automático instalada.

Vea la explicación a continuación para saber cómo repelemse usa. La diferencia entre este más corto y el siguiente es que la caja de herramientas S&ML incluye la función datasampleque se puede usar para tomar uno o más elementos de una matriz al azar (con probabilidad uniforme) que permite usar una función anónima, eliminando elinput/disp llamadas.

MATLAB, 49 bytes

n=input('');a=repelem(n,n);disp(a(randi(nnz(a))))

Este código supone que se usa MATLAB R2015a o más reciente, ya que es cuando repelemse introdujo la función.repelemes una función que toma dos parámetros, el primero es una matriz de números que se replicarán y el segundo es una matriz de cuántas veces se debe replicar el elemento correspondiente. Esencialmente, la función realiza la decodificación de longitud de ejecución proporcionando el número y la longitud de ejecución.

Al proporcionar la misma entrada a ambas entradas repelem, terminamos con una matriz que consta de n veces más del elemento n si eso tiene sentido. Si lo proporcionaras [1 2 3]obtendrías [1 2 2 3 3 3]. Si lo proporcionaras [1 2 4 2]obtendrías [1 2 2 4 4 4 4 2 2]. Al hacer esto, significa que si seleccionamos un elemento con probabilidad uniforme ( randi(m)da un número entero aleatorio de 1 am con probabilidad uniforme), cada elemento n tiene una probabilidad n veces mayor de ser seleccionado. En el primer ejemplo de [1 2 3], 1tendría una probabilidad de 1/6, 2tendría una probabilidad de 2/6 y 3tendría una probabilidad de 3/6.


Como nota al margen, debido a que repelemaún no está disponible para Octave, no puedo dar un enlace TIO. Además, debido a que Octave no se puede usar, hay una gran penalización de caracteres input()y disp()no es posible usarlo como una función anónima. Si Octave es compatible repelem, se podría utilizar lo siguiente:

@(n)a(randi(nnz(a=repelem(n,n))))

Eso habría ahorrado 16 bytes, pero no fue así.

Tom Carpenter
fuente
Realmente aprecio la explicación, gracias!
Ian H.