Crie uma função que produza um conjunto de números aleatórios distintos, extraídos de um intervalo. A ordem dos elementos no conjunto não é importante (eles podem até ser classificados), mas deve ser possível que o conteúdo do conjunto seja diferente cada vez que a função é chamada.

A função receberá 3 parâmetros na ordem que desejar:

1. Contagem de números no conjunto de saída
2. Limite inferior (inclusive)
3. Limite superior (inclusive)

Suponha que todos os números sejam inteiros no intervalo de 0 (inclusive) a 2 ³¹ (exclusivo). A saída pode ser transmitida da maneira que você desejar (escreva no console, como uma matriz, etc.)

A julgar

Os critérios incluem os 3 R's

1. Tempo de execução - testado em uma máquina Windows 7 de quatro núcleos com qualquer compilador disponível de forma fácil ou gratuita (forneça um link, se necessário)
2. Robustez - a função lida com casos de canto ou cairá em um loop infinito ou produzirá resultados inválidos - uma exceção ou erro na entrada inválida é válido
3. Aleatoriedade - deve produzir resultados aleatórios que não são facilmente previsíveis com uma distribuição aleatória. Usar o gerador de números aleatórios incorporado é bom. Mas não deve haver preconceitos óbvios ou padrões previsíveis óbvios. Precisa ser melhor do que o gerador de números aleatórios usado pelo Departamento de Contabilidade em Dilbert

Se for robusto e aleatório, o tempo de execução será reduzido. Deixar de ser robusto ou aleatório prejudica muito sua posição.

Pitão

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

Provavelmente acabei de reinventar algum algoritmo conhecido, mas a idéia é (conceitualmente) executar um embaralhamento parcial de Fisher-Yates do intervalo lower..upperpara obter o nprefixo de comprimento de um intervalo uniformemente embaralhado.

Obviamente, armazenar todo o intervalo seria bastante caro, então eu só guardo os locais onde os elementos foram trocados.

Dessa forma, o algoritmo deve ter um bom desempenho tanto no caso em que você está amostrando números de um intervalo restrito (por exemplo, 1000 números no intervalo de 1..1000) quanto no caso em que você está amostrando números de um amplo intervalo .

Não tenho certeza sobre a qualidade da aleatoriedade do gerador interno em Python, mas é relativamente simples trocar qualquer gerador que possa gerar números inteiros uniformemente de algum intervalo.

python 2.7

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

Não sei ao certo qual é a sua posição usando métodos aleatórios integrados, mas aqui está você de qualquer maneira. agradável e curto

edit: notei que range () não gosta de fazer grandes listas. resulta em um erro de memória. vai ver se existe alguma outra maneira de fazer isso ...

edit2: range foi a função errada, o xrange funciona. O número máximo máximo é realmente 2**31-1para python

teste:

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

C

Retorna uma matriz contendo x entradas aleatórias únicas entre min e max. (o chamador deve 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 gerando x números inteiros aleatórios seqüenciais no intervalo e embaralhando-os. Adicione umseed(time) lugar no chamador se você não quiser os mesmos resultados a cada execução.

Ruby> = 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)

A pergunta não está correta. Você precisa de amostragem uniforme ou não? No caso de amostragem uniforme ser necessária, tenho o código a seguir em R, que tem complexidade média O ( s log s ), onde s é o tamanho da amostra.

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

Obviamente, pode-se reescrevê-lo em C para obter melhor desempenho. A complexidade desse algoritmo é discutida em: Rouzankin, PS; Voytishek, AV Sobre o custo de algoritmos para seleção aleatória. Métodos de Monte Carlo Appl. 5 (1999), n. 1, 39-54. http://dx.doi.org/10.1515/mcma.1999.5.1.39

Você pode procurar neste artigo outro algoritmo com a mesma complexidade média.

Mas se você não precisa de amostragem uniforme, exigindo apenas que todos os números amostrados sejam diferentes, a situação muda drasticamente. Não é difícil escrever um algoritmo que possua complexidade média O ( s ).

Veja também para amostragem uniforme: P. Gupta, GP Bhattacharjee. (1984) Um algoritmo eficiente para amostragem aleatória sem substituição. International Journal of Computer Mathematics 16: 4, páginas 201-209. DOI: 10.1080 / 00207168408803438

Teuhola, J. e Nevalainen, O. 1982. Dois algoritmos eficientes para amostragem aleatória sem substituição. / IJCM /, 11 (2): 127–140. DOI: 10.1080 / 00207168208803304

No último artigo, os autores usam tabelas de hash e afirmam que seus algoritmos têm complexidade O ( s ). Há mais um algoritmo de tabela de hash rápido, que será implementado em breve no pqR (bastante rápido R): https://stat.ethz.ch/pipermail/r-devel/2017-October/075012.html

APL, 18 22 bytes

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

Declara uma função anônima que recebe dois argumentos ⍺e ⍵. ⍺é o número de números aleatórios que você deseja, ⍵é um vetor que contém os limites inferior e superior, nessa ordem.

a?bescolhe anúmeros aleatórios entre 0 e bsem substituição. Ao tomar ⍵[1]-⍵[0], obtemos o tamanho do intervalo. Em seguida, escolhemos os ⍺números (veja abaixo) desse intervalo e adicionamos o limite inferior. Em C, isso seria

lower + rand() * (upper - lower)

⍺vezes sem substituição. Parênteses não necessários porque o APL opera da direita para a esquerda.

Supondo que eu tenha entendido as condições corretamente, isso falha nos critérios de 'robustez' porque a função falhará se dados argumentos incorretos (por exemplo, passando um vetor em vez de um escalar como ⍺ ).

No caso de ⍺um vetor e não um escalar, 1↑⍺assume o primeiro elemento de ⍺. Para um escalar, esse é o próprio escalar. Para um vetor, é o primeiro elemento. Isso deve fazer com que a função atenda aos critérios de 'robustez'.

Exemplo:

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

compile e execute:

scalac RandSetRunner.scala 
scala RandSetRunner 200 15 0 100

A segunda linha executará 200 testes com 15 valores de 0 a 100, porque o Scala produz bytecode rápido, mas precisa de algum tempo de inicialização. Assim, 200 partidas com 15 valores de 0 a 100 consumiriam mais tempo.

Amostra em um núcleo único de 2 Ghz:

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

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

Lógica:

Usando os números aleatórios e recursivamente incorporados no intervalo (max-min), adicionando min e verificando se o tamanho do conjunto é o tamanho esperado.

Crítica:

• Será rápido para pequenas amostras de grandes intervalos, mas se a tarefa for selecionar quase todos os elementos de uma amostra (999 números em 1000), ela escolherá repetidamente números, já no conjunto.
• A partir da pergunta, não tenho certeza se devo sanear solicitações não realizáveis, como Tomar 10 números distintos de 4 a 8. Isso agora levará a um loop sem fim, mas pode ser facilmente evitado com uma verificação prévia que acrescentarei se Requeridos.

Esquema

Não sei por que você precisa de 3 parâmetros passados ​​nem por que eu preciso assumir qualquer faixa ...

(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 ++

Esse código é melhor ao desenhar muitas amostras do intervalo.

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

Em seguida, use f [x; y; z] como [contagem de números no conjunto de saída; ponto inicial; tamanho do intervalo]

por exemplo, f [5; 10; 10] produzirá 5 números aleatórios distintos entre 10 e 19, inclusive.

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

Os resultados acima mostram o desempenho em 100.000 iterações, escolhendo 100 números aleatórios entre 1 e 10.000.

R, 31 ou 40 bytes (dependendo do significado da palavra "intervalo")

Se a entrada tiver 3 números, a[1], a[2], a[3]e por "intervalo" você quer dizer "uma sequência inteira de [2] a [3]", então você tem o seguinte:

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

Se você tiver uma matriz nda qual você está prestes a reamostrar, mas sob a restrição dos limites inferior e superior, como "reamostrar valores da matriz especificada nno intervalo a[1]...a[2]", use o seguinte:

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

Estou bastante surpreso por o resultado anterior não ter sido jogado no golfe, considerando a amostra incorporada com instalações de substituição! Criamos um vetor que satisfaz a condição do intervalo e o amostramos novamente.

• Robustez: os casos de canto (sequências do mesmo comprimento que o intervalo para amostragem) são tratados por padrão.
• Tempo de execução: extremamente rápido porque está embutido.
• Aleatoriedade: a semente é alterada automaticamente toda vez que o RNG é chamado.

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

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

Link para lib: https://github.com/mvegh1/Enumerable/

Explicação do código: A expressão Lambda aceita min, max, count como args. Crie uma coleção de tamanho n e mapeie cada elemento para um número aleatório que atenda aos critérios mínimo / máximo. Converta na matriz JS nativa e retorne-a. Eu executei isso também em uma entrada de tamanho 5.000.000 e, após aplicar uma transformação distinta, ainda mostrei 5.000.000 de elementos. Se for acordado que isso não é seguro o suficiente para garantir a distinção, atualizarei a resposta

Incluí algumas estatísticas na imagem abaixo ...

EDIT: A imagem abaixo mostra o código / desempenho que garante que cada elemento será distinto. É muito mais lento (6,65 segundos para 50.000 elementos) do que o código original acima para os mesmos argumentos (0,012 segundos)

K (oK) , 14 bytes

Solução:

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

Experimente online!

Exemplo:

> {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

Explicação:

Toma 3 entradas implícitas por especificação:

• x, contagem de números no conjunto de saída,
• y, limite inferior (inclusive)
• z, limite 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:

Também um poliglota q/kdb+com um conjunto extra de colchetes: {y+((-)x)?1+z-y}(16 bytes).

Axiom + sua 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

A função f () acima retorna como erro a lista vazia, no caso f (n, a, b) com a> b. Em outros casos de entrada inválida, ela não é executada com uma mensagem de erro na janela do Axiom, porque o argumento não será do tipo correto. Exemplos

(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