Cree una función que genere un conjunto de números aleatorios distintos extraídos de un rango. El orden de los elementos en el conjunto no es importante (incluso se pueden ordenar), pero debe ser posible que el contenido del conjunto sea diferente cada vez que se llama a la función.

La función recibirá 3 parámetros en el orden que desee:

1. Recuento de números en el conjunto de salida
2. Límite inferior (incluido)
3. Límite superior (incluido)

Suponga que todos los números son enteros en el rango de 0 (inclusive) a 2 ³¹ (exclusivo). La salida se puede devolver de la forma que desee (escriba en la consola, como una matriz, etc.)

Juzgar

Los criterios incluyen las 3 R's

1. Tiempo de ejecución : probado en una máquina Windows 7 de cuatro núcleos con cualquier compilador que esté disponible de forma libre o fácil (proporcione un enlace si es necesario)
2. Robustez : la función maneja casos de esquina o caerá en un bucle infinito o producirá resultados no válidos: una excepción o error en una entrada no válida es válida
3. Aleatoriedad : debe producir resultados aleatorios que no son fácilmente predecibles con una distribución aleatoria. Usar el generador de números aleatorios incorporado está bien. Pero no debe haber sesgos obvios o patrones predecibles obvios. Necesita ser mejor que ese generador de números aleatorios utilizado por el Departamento de Contabilidad en Dilbert

Si es robusto y aleatorio, todo se reduce al tiempo de ejecución. No ser robusto o aleatorio perjudica enormemente su clasificación.

Pitón

import random

def sample(n, lower, upper):
    result = []
    pool = {}
    for _ in xrange(n):
        i = random.randint(lower, upper)
        x = pool.get(i, i)
        pool[i] = pool.get(lower, lower)
        lower += 1
        result.append(x)
    return result

Probablemente solo reinventé un algoritmo bien conocido, pero la idea es realizar (conceptualmente) una combinación aleatoria parcial de Fisher-Yates del rango lower..upperpara obtener el nprefijo de longitud de un rango aleatorio uniforme.

Por supuesto, almacenar todo el rango sería bastante costoso, por lo que solo almaceno los lugares donde se han intercambiado los elementos.

De esta manera, el algoritmo debería funcionar bien tanto en el caso de que esté muestreando números de un rango estrecho (por ejemplo, 1000 números en el rango 1..1000), como en el caso de que esté muestreando números de un rango amplio .

No estoy seguro de la calidad de la aleatoriedad del generador incorporado en Python, pero es relativamente simple intercambiar cualquier generador que pueda generar enteros de manera uniforme desde algún rango.

python 2.7

import random
print(lambda x,y,z:random.sample(xrange(y,z),x))(input(),input(),input())

no estoy seguro de cuál es tu posición usando métodos aleatorios incorporados, pero aquí tienes de todos modos. agradable y corto

editar: acabo de notar que a range () no le gusta hacer grandes listas. da como resultado un error de memoria. verá si hay alguna otra forma de hacer esto ...

edit2: range fue la función incorrecta, xrange funciona. El número entero máximo es en realidad 2**31-1para python

prueba:

python sample.py
10
0
2**31-1
[786475923, 2087214992, 951609341, 1894308203, 173531663, 211170399, 426989602, 1909298419, 1424337410, 2090382873]

C

Devuelve una matriz que contiene x entradas aleatorias únicas entre min y max. (la persona que llama debe liberar)

#include <stdlib.h>
#include <stdint.h>
#define MAX_ALLOC ((uint32_t)0x40000000)  //max allocated bytes, fix per platform
#define MAX_SAMPLES (MAX_ALLOC/sizeof(uint32_t))

int* randsamp(uint32_t x, uint32_t min, uint32_t max)
{
   uint32_t r,i=x,*a;
   if (!x||x>MAX_SAMPLES||x>(max-min+1)) return NULL;
   a=malloc(x*sizeof(uint32_t));
   while (i--) {
      r= (max-min+1-i);
      a[i]=min+=(r ? rand()%r : 0);
      min++;
   }
   while (x>1) {
      r=a[i=rand()%x--];
      a[i]=a[x];
      a[x]=r;
   }
   return a;
}

Funciona generando x enteros aleatorios secuenciales en el rango, luego barajándolos. Agregue un seed(time)lugar en la persona que llama si no desea los mismos resultados en cada ejecución.

Rubí> = 1.8.7

def pick(num, min, max)
  (min..max).to_a.sample(num)
end

p pick(5, 10, 20) #=>[12, 18, 13, 11, 10]

R

s <- function(n, lower, upper) sample(lower:upper,n); s(10,0,2^31-2)

La pregunta no es correcta. ¿Necesita un muestreo uniforme o no? En el caso de que se necesite un muestreo uniforme, tengo el siguiente código en R, que tiene una complejidad promedio O ( s log s ), donde s es el tamaño de la muestra.

# The Tree growing algorithm for uniform sampling without replacement
# by Pavel Ruzankin 
quicksample = function (n,size)
# n - the number of items to choose from
# size - the sample size
{
  s=as.integer(size)
  if (s>n) {
    stop("Sample size is greater than the number of items to choose from")
  }
  # upv=integer(s) #level up edge is pointing to
  leftv=integer(s) #left edge is poiting to; must be filled with zeros
  rightv=integer(s) #right edge is pointig to; must be filled with zeros
  samp=integer(s) #the sample
  ordn=integer(s) #relative ordinal number

  ordn[1L]=1L #initial value for the root vertex
  samp[1L]=sample(n,1L) 
  if (s > 1L) for (j in 2L:s) {
    curn=sample(n-j+1L,1L) #current number sampled
    curordn=0L #currend ordinal number
    v=1L #current vertice
    from=1L #how have come here: 0 - by left edge, 1 - by right edge
    repeat {
      curordn=curordn+ordn[v]
      if (curn+curordn>samp[v]) { #going down by the right edge
        if (from == 0L) {
          ordn[v]=ordn[v]-1L
        }
        if (rightv[v]!=0L) {
          v=rightv[v]
          from=1L
        } else { #creating a new vertex
          samp[j]=curn+curordn
          ordn[j]=1L
          # upv[j]=v
          rightv[v]=j
          break
        }
      } else { #going down by the left edge
        if (from==1L) {
          ordn[v]=ordn[v]+1L
        }
        if (leftv[v]!=0L) {
          v=leftv[v]
          from=0L
        } else { #creating a new vertex
          samp[j]=curn+curordn-1L
          ordn[j]=-1L
          # upv[j]=v
          leftv[v]=j
          break
        }
      }
    }
  }
  return(samp)  
}

Por supuesto, uno puede reescribirlo en C para un mejor rendimiento. La complejidad de este algoritmo se discute en: Rouzankin, PS; Voytishek, AV Sobre el costo de los algoritmos para la selección aleatoria. Métodos Monte Carlo Appl. 5 (1999), no. 1, 39-54. http://dx.doi.org/10.1515/mcma.1999.5.1.39

Puede buscar en este documento otro algoritmo con la misma complejidad promedio.

Pero si no necesita un muestreo uniforme, que solo requiere que todos los números muestreados sean diferentes, entonces la situación cambia dramáticamente. No es difícil escribir un algoritmo que tenga O ( s ) de complejidad promedio .

Ver también para muestreo uniforme: P. Gupta, GP Bhattacharjee. (1984) Un algoritmo eficiente para muestreo aleatorio sin reemplazo. International Journal of Computer Mathematics 16: 4, páginas 201-209. DOI: 10.1080 / 00207168408803438

Teuhola, J. y Nevalainen, O. 1982. Dos algoritmos eficientes para muestreo aleatorio sin reemplazo. / IJCM /, 11 (2): 127–140. DOI: 10.1080 / 00207168208803304

En el último artículo, los autores usan tablas hash y afirman que sus algoritmos tienen O ( s ) complejidad. Hay un algoritmo más rápido de tabla hash, que pronto se implementará en pqR (R bastante rápido): https://stat.ethz.ch/pipermail/r-devel/2017-October/075012.html

APL, 18 22 bytes

{⍵[0]+(1↑⍺)?⍵[1]-⍵[0]}

Declara una función anónima que toma dos argumentos ⍺y ⍵. ⍺es el número de números aleatorios que desea, ⍵es un vector que contiene los límites inferior y superior, en ese orden.

a?bselecciona anúmeros aleatorios entre 0- bsin reemplazo. Al tomar ⍵[1]-⍵[0]obtenemos el tamaño del rango. Luego elegimos los ⍺números (ver más abajo) de ese rango y agregamos el límite inferior. En C, esto sería

lower + rand() * (upper - lower)

⍺veces sin reemplazo. No se necesitan paréntesis porque APL funciona de derecha a izquierda.

Suponiendo que he entendido las condiciones correctamente, esto falla los criterios de 'robustez' porque la función fallará si se le dan argumentos incorrectos (por ejemplo, pasar un vector en lugar de un escalar como ⍺).

En el caso de que ⍺sea ​​un vector en lugar de un escalar, 1↑⍺toma el primer elemento de ⍺. Para un escalar, este es el escalar en sí. Para un vector, es el primer elemento. Esto debería hacer que la función cumpla con los criterios de 'robustez'.

Ejemplo:

Input: 100 {⍵[0]+⍺?⍵[1]-⍵[0]} 0 100
Output: 34 10 85 2 46 56 32 8 36 79 77 24 90 70 99 61 0 21 86 50 83 5 23 27 26 98 88 66 58 54 76 20 91 72 71 65 63 15 33 11 96 60 43 55 30 48 73 75 31 13 19 3 45 44 95 57 97 37 68 78 89 14 51 47 74 9 67 18 12 92 6 49 41 4 80 29 82 16 94 52 59 28 17 87 25 84 35 22 38 1 93 81 42 40 69 53 7 39 64 62

Scala

object RandSet {
  val random = util.Random 

  def rand (count: Int, lower: Int, upper: Int, sofar: Set[Int] = Set.empty): Set[Int] =
    if (count == sofar.size) sofar else 
    rand (count, lower, upper, sofar + (random.nextInt (upper-lower) + lower)) 
}

object RandSetRunner {

  def main (args: Array [String]) : Unit = {
    if (args.length == 4) 
      (0 until args (0).toInt).foreach { unused => 
      println (RandSet.rand (args (1).toInt, args (2).toInt, args (3).toInt).mkString (" "))
    }
    else Console.err.println ("usage: scala RandSetRunner OUTERCOUNT COUNT MIN MAX")
  }
}

compilar y ejecutar:

scalac RandSetRunner.scala 
scala RandSetRunner 200 15 0 100

La segunda línea ejecutará 200 pruebas con 15 valores de 0 a 100, porque Scala produce un código de bytes rápido pero necesita algo de tiempo de inicio. Entonces 200 comienza con 15 valores de 0 a 100 consumiría más tiempo.

Muestra en un solo núcleo de 2 Ghz:

time scala RandSetRunner 100000 10 0 1000000 > /dev/null

real    0m2.728s
user    0m2.416s
sys     0m0.168s

Lógica:

Usando los números aleatorios y recursivos incorporados en el rango (max-min), sumando min y comprobando, si el tamaño del conjunto es el tamaño esperado.

Crítica:

• Será rápido para muestras pequeñas de grandes rangos, pero si la tarea es elegir casi todos los elementos de una muestra (999 números de 1000), elegirá números repetidamente, ya en el conjunto.
• A partir de la pregunta, no estoy seguro, si tengo que desinfectar contra solicitudes que no se pueden completar, como Tomar 10 números distintos del 4 al 8. Esto ahora conducirá a un bucle sin fin, pero se puede evitar fácilmente con una verificación previa que agregaré si pedido.

Esquema

No estoy seguro de por qué necesita pasar 3 parámetros ni por qué necesito asumir cualquier rango ...

(import srfi-1) ;; for iota
(import srfi-27) ;; randomness
(import srfi-43) ;; for vector-swap!

(define rand (random-source-make-integers
               default-random-source))

;; n: length, i: lower limit
(define (random-range n i)
  (let ([v (list->vector (iota n i))])
    (let f ([n n])
      (let* ([i (rand n)] [n (- n 1)])
        (if (zero? n) v
            (begin (vector-swap! v n i) (f n)))))))

R

random <- function(count, from, to) {
  rand.range <- to - from

  vec <- c()

  for (i in 1:count) {
    t <- sample(rand.range, 1) + from
    while(i %in% vec) {
      t <- sample(rand.range, 1) + from
    }
    vec <- c(vec, t)
  }

  return(vec)
}

C ++

Este código es mejor cuando se extraen muchas muestras del rango.

#include <exception>
#include <stdexcept>
#include <cstdlib>

template<typename OutputIterator>
 void sample(OutputIterator out, int n, int min, int max)
{
  if (n < 0)
    throw std::runtime_error("negative sample size");
  if (max < min)
    throw std::runtime_error("invalid range");
  if (n > max-min+1)
    throw std::runtime_error("sample size larger than range");

  while (n>0)
  {
    double r = std::rand()/(RAND_MAX+1.0);
    if (r*(max-min+1) < n)
    {
      *out++ = min;
      --n;
    }
    ++min;
  }
}

Q (19 caracteres)

f:{(neg x)?y+til z}

Luego use f [x; y; z] como [conteo de números en el conjunto de salida; punto de partida; tamaño del rango]

por ejemplo, f [5; 10; 10] generará 5 números aleatorios distintos entre 10 y 19 inclusive.

q)\ts do[100000;f[100;1;10000]]
2418 131456j

Los resultados anteriores muestran el rendimiento en 100,000 iteraciones de elegir 100 números aleatorios entre 1 y 10,000.

R, 31 o 40 bytes (dependiendo del significado de la palabra "rango")

Si la entrada tiene 3 números, a[1], a[2], a[3]y por "rango" quieres decir "una secuencia entera de un [2] a un [3]", entonces tienes esto:

a=scan();sample(a[2]:a[3],a[1])

Si tiene una matriz nde la cual está a punto de volver a muestrear, pero bajo la restricción de los límites inferior y superior, como "valores de remuestreo de la matriz dada ndel rango a[1]...a[2]", utilice esto:

a=scan();sample(n[n>=a[2]&n<=a[3]],a[1])

¡Estoy bastante sorprendido de por qué el resultado anterior no se jugó considerando la muestra incorporada con instalaciones de reemplazo! Creamos un vector que satisface la condición del rango y lo volvemos a muestrear.

• Robustez: los casos de esquina (secuencias de la misma longitud que el rango para muestrear) se manejan por defecto.
• Tiempo de ejecución: extremadamente rápido porque está integrado.
• Aleatoriedad: la semilla se cambia automáticamente cada vez que se invoca el RNG.

Javascript (usando una biblioteca externa) (64 bytes / 104 bytes ??)

(a,b,n)=>_.Range(0,n).Select(x=>Math.random()*(b-a)+a).ToArray()

Enlace a lib: https://github.com/mvegh1/Enumerable/

Explicación del código: la expresión Lambda acepta min, max, count como args. Cree una colección de tamaño n y asigne cada elemento a un número aleatorio que se ajuste a los criterios mínimo / máximo. Convierta a matriz JS nativa y devuélvala. También ejecuté esto en una entrada de tamaño 5,000,000, y después de aplicar una transformación distinta todavía mostraba 5,000,000 elementos. Si se acuerda que esto no es lo suficientemente seguro como garantía de distinción, actualizaré la respuesta

Incluí algunas estadísticas en la imagen a continuación ...

EDITAR: La imagen a continuación muestra el código / rendimiento que garantiza que cada elemento será distinto. Es mucho más lento (6.65 segundos para 50,000 elementos) en comparación con el código original anterior para los mismos argumentos (0.012 segundos)

K (oK) , 14 bytes

Solución:

{y+(-x)?1+z-y}

Pruébalo en línea!

Ejemplo:

> {y+(-x)?1+z-y}. 10 10 20      / note: there are two ways to provide input, dot or
13 20 16 17 19 10 14 12 11 18
> {y+(-x)?1+z-y}[10;10;20]      / explicitly with [x;y;z]
12 11 13 19 15 17 18 20 14 10

Explicación:

Toma 3 entradas implícitas por especificación:

• x, recuento de números en el conjunto de salida,
• y, límite inferior (inclusive)
• z, límite superior (inclusive)

{y+(-x)?1+z-y} / the solution
{            } / lambda function with x, y and z as implicit inputs
          z-y  / subtract lower limit from upper limit
        1+     / add 1
   (-x)?       / take x many distinct items from 0..(1+z=y)
 y+            / add lower limit

Notas:

También un políglota q/kdb+con un conjunto adicional de paréntesis: {y+((-)x)?1+z-y}(16 bytes).

Axioma + su biblioteca

f(n:PI,a:INT,b:INT):List INT==
    r:List INT:=[]
    a>b or n>99999999 =>r
    d:=1+b-a
    for i in 1..n repeat
          r:=concat(r,a+random(d)$INT)
    r

La función f () anterior devuelve como error la lista vacía, en el caso f (n, a, b) con a> b. En otros casos de entrada no válida, no se ejecuta con un mensaje de error en la ventana de Axiom, porque el argumento no será del tipo correcto. Ejemplos

(6) -> f(1,1,5)
   (6)  [2]
                                                       Type: List Integer
(7) -> f(1,1,1)
   (7)  [1]
                                                       Type: List Integer
(10) -> f(10,1,1)
   (10)  [1,1,1,1,1,1,1,1,1,1]
                                                       Type: List Integer
(11) -> f(10,-20,-1)
   (11)  [- 10,- 4,- 18,- 5,- 5,- 11,- 15,- 1,- 20,- 1]
                                                       Type: List Integer
(12) -> f(10,-20,-1)
   (12)  [- 4,- 5,- 3,- 4,- 18,- 1,- 2,- 14,- 19,- 8]
                                                       Type: List Integer
(13) -> f(10,-20,-1)
   (13)  [- 18,- 12,- 12,- 19,- 19,- 15,- 5,- 17,- 19,- 4]
                                                       Type: List Integer
(14) -> f(10,-20,-1)
   (14)  [- 8,- 11,- 20,- 10,- 4,- 8,- 11,- 3,- 10,- 16]
                                                       Type: List Integer
(15) -> f(10,9,-1)
   (15)  []
                                                       Type: List Integer
(16) -> f(10,0,100)
   (16)  [72,83,41,35,27,0,33,18,60,38]
                                                       Type: List Integer