Créez une fonction qui produira un ensemble de nombres aléatoires distincts tirés d'une plage. L'ordre des éléments de l'ensemble est sans importance (ils peuvent même être triés), mais il doit être possible que le contenu de l'ensemble soit différent à chaque appel de la fonction.

La fonction recevra 3 paramètres dans l'ordre que vous souhaitez:

1. Nombre de nombres dans le jeu de sortie
2. Limite inférieure (incluse)
3. Limite supérieure (incluse)

Supposons que tous les nombres sont des entiers compris entre 0 (inclus) et 2 ³¹ (exclusif). La sortie peut être renvoyée comme vous le souhaitez (écriture sur la console, sous forme de tableau, etc.)

Juger

Les critères incluent les 3 R

1. Exécution - testé sur une machine quadricœur Windows 7 avec le compilateur disponible librement ou facilement (fournissez un lien si nécessaire)
2. Robustesse - la fonction gère-t-elle les cas d'angle ou va-t-elle tomber dans une boucle infinie ou produire des résultats invalides - une exception ou une erreur sur une entrée invalide est valide
3. Randomness - il devrait produire des résultats aléatoires qui ne sont pas facilement prévisibles avec une distribution aléatoire. L'utilisation du générateur de nombres aléatoires intégré est très bien. Mais il ne devrait pas y avoir de biais évidents ni de schémas prévisibles évidents. Doit être meilleur que ce générateur de nombres aléatoires utilisé par le service de comptabilité de Dilbert

S'il est robuste et aléatoire, il se résume à l'exécution. Ne pas être robuste ou aléatoire nuit grandement à son classement.

Python

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

J'ai probablement juste réinventé un algorithme bien connu, mais l'idée est d'effectuer (conceptuellement) un shuffle partiel de Fisher-Yates de la plage lower..upperpour obtenir le npréfixe de longueur d'une plage uniformément mélangée.

Bien sûr, le stockage de toute la gamme serait plutôt coûteux, donc je ne stocke que les emplacements où les éléments ont été échangés.

De cette façon, l'algorithme devrait bien fonctionner à la fois dans le cas où vous échantillonnez des nombres à partir d'une plage étroite (par exemple 1000 nombres dans la plage 1 à 1000), ainsi que dans le cas où vous échantillonnez des nombres à partir d'une large plage .

Je ne suis pas sûr de la qualité du caractère aléatoire du générateur intégré en Python, mais il est relativement simple d'échanger n'importe quel générateur qui peut générer uniformément des entiers à partir d'une certaine plage.

python 2.7

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

Je ne sais pas quel est votre statut en utilisant des méthodes aléatoires intégrées, mais vous y allez quand même. agréable et court

edit: vient de remarquer que range () n'aime pas faire de grandes listes. entraîne une erreur de mémoire. verra s'il y a une autre façon de le faire ...

edit2: la plage n'était pas la bonne fonction, xrange fonctionne. L'entier maximum est en fait 2**31-1pour python

tester:

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

C

Renvoie un tableau contenant x entrées aléatoires uniques entre min et max. (l'appelant doit libérer)

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

Fonctionne en générant x entiers aléatoires séquentiels dans la plage, puis en les mélangeant. Ajoutez un seed(time)endroit dans l'appelant si vous ne voulez pas les mêmes résultats à chaque exécution.

Rubis> = 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 question n'est pas correcte. Avez-vous besoin d'un échantillonnage uniforme ou non? Dans le cas où un échantillonnage uniforme est nécessaire, j'ai le code suivant dans R, qui a une complexité moyenne O ( s log s ), où s est la taille de l'échantillon.

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

Bien sûr, on peut le réécrire en C pour de meilleures performances. La complexité de cet algorithme est discutée dans: Rouzankin, PS; Voytishek, AV Sur le coût des algorithmes de sélection aléatoire. Méthodes de Monte Carlo Appl. 5 (1999), no. 1, 39-54. http://dx.doi.org/10.1515/mcma.1999.5.1.39

Vous pouvez chercher dans cet article un autre algorithme avec la même complexité moyenne.

Mais si vous n'avez pas besoin d'un échantillonnage uniforme, exigeant seulement que tous les nombres échantillonnés soient différents, la situation change radicalement. Il n'est pas difficile d'écrire un algorithme qui a une complexité moyenne O ( s ).

Voir aussi pour un échantillonnage uniforme: P. Gupta, GP Bhattacharjee. (1984) Un algorithme efficace pour l'échantillonnage aléatoire sans remplacement. Journal international de mathématiques informatiques 16: 4, pages 201-209. DOI: 10.1080 / 00207168408803438

Teuhola, J. et Nevalainen, O. 1982. Deux algorithmes efficaces pour l'échantillonnage aléatoire sans remplacement. / IJCM /, 11 (2): 127–140. DOI: 10.1080 / 00207168208803304

Dans le dernier article, les auteurs utilisent des tables de hachage et affirment que leurs algorithmes ont une complexité O ( s ). Il existe un autre algorithme de table de hachage rapide, qui sera bientôt implémenté dans pqR (assez rapide R): https://stat.ethz.ch/pipermail/r-devel/2017-October/075012.html

APL, 18 22 octets

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

Déclare une fonction anonyme qui prend deux arguments ⍺et ⍵. ⍺est le nombre de nombres aléatoires que vous souhaitez, ⍵est un vecteur contenant les bornes inférieure et supérieure, dans cet ordre.

a?bchoisit ades nombres aléatoires entre 0 et bsans remplacement. En prenant, ⍵[1]-⍵[0]nous obtenons la taille de la plage. Ensuite, nous choisissons des ⍺nombres (voir ci-dessous) dans cette plage et ajoutons la borne inférieure. En C, ce serait

lower + rand() * (upper - lower)

⍺fois sans remplacement. Les parenthèses ne sont pas nécessaires car APL fonctionne de droite à gauche.

En supposant que j'ai bien compris les conditions, cela échoue aux critères de «robustesse» car la fonction échouera si on lui donne des arguments incorrects (par exemple en passant un vecteur au lieu d'un scalaire ⍺).

Dans le cas où il ⍺s'agit d'un vecteur plutôt que d'un scalaire, 1↑⍺prend le premier élément de ⍺. Pour un scalaire, c'est le scalaire lui-même. Pour un vecteur, c'est le premier élément. Cela devrait faire en sorte que la fonction réponde aux critères de «robustesse».

Exemple:

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

compiler et exécuter:

scalac RandSetRunner.scala 
scala RandSetRunner 200 15 0 100

La deuxième ligne exécutera 200 tests avec 15 valeurs de 0 à 100, car Scala produit un bytecode rapide mais nécessite un certain temps de démarrage. Ainsi, 200 départs avec 15 valeurs de 0 à 100 prendraient plus de temps.

Exemple sur un monocœur 2 Ghz:

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

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

Logique:

Utiliser les nombres aléatoires et de manière récursive intégrés dans la plage (max-min), ajouter min et vérifier si la taille de l'ensemble est la taille attendue.

La critique:

• Il sera rapide pour de petits échantillons de grandes plages, mais si la tâche consiste à sélectionner presque tous les éléments d'un échantillon (999 numéros sur 1000), il choisira à plusieurs reprises des numéros, déjà dans l'ensemble.
• De la question, je ne suis pas sûr, si je dois me désinfecter contre les demandes insatisfaisantes comme Prendre 10 numéros distincts de 4 à 8. Cela mènera maintenant à une boucle sans fin, mais peut facilement être évité avec une vérification préalable que j'ajouterai si demandé.

Schème

Je ne sais pas pourquoi vous avez besoin de 3 paramètres passés ni pourquoi je dois assumer une plage ...

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

Ce code est préférable lors du prélèvement de nombreux échantillons de la plage.

#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 caractères)

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

Utilisez ensuite f [x; y; z] comme [nombre de nombres dans l'ensemble de sortie; point de départ; taille de la plage]

Par exemple, f [5; 10; 10] produira 5 nombres aléatoires distincts entre 10 et 19 inclus.

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

Les résultats ci-dessus montrent des performances à 100 000 itérations de sélection de 100 nombres aléatoires entre 1 et 10 000.

R, 31 ou 40 octets (selon la signification du mot «plage»)

Si l'entrée a 3 nombres, a[1], a[2], a[3]et par "plage" vous voulez dire "une séquence entière d'un [2] à un [3]", alors vous avez ceci:

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

Si vous avez un tableau à npartir duquel vous êtes sur le point de rééchantillonner, mais sous la restriction des limites inférieure et supérieure, comme «rééchantillonner les valeurs du tableau donné à npartir de la plage a[1]...a[2]», alors utilisez ceci:

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

Je suis assez surpris de constater que le résultat précédent n'a pas été joué au vu de l'échantillon intégré avec des installations de remplacement! Nous créons un vecteur qui satisfait la condition de plage et le ré-échantillonnons.

• Robustesse: les cas d'angle (séquences de la même longueur que la plage à échantillonner) sont traités par défaut.
• Temps d'exécution: extrêmement rapide car il est intégré.
• Aléatoire: la graine est automatiquement changée chaque fois que le RNG est invoqué.

Javascript (en utilisant une bibliothèque externe) (64 octets / 104 octets ??)

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

Lien vers la bibliothèque: https://github.com/mvegh1/Enumerable/

Explication du code: l'expression Lambda accepte min, max, compte comme arguments. Créez une collection de taille n et mappez chaque élément à un nombre aléatoire correspondant aux critères min / max. Convertissez en tableau JS natif et renvoyez-le. J'ai également exécuté cela sur une entrée de taille 5 000 000, et après avoir appliqué une transformation distincte, j'ai toujours montré 5 000 000 d'éléments. S'il est convenu que ce n'est pas suffisamment sûr pour garantir la distinction, je mettrai à jour la réponse

J'ai inclus quelques statistiques dans l'image ci-dessous ...

EDIT: L'image ci-dessous montre le code / les performances qui garantissent que chaque élément sera distinct. C'est beaucoup plus lent (6,65 secondes pour 50000 éléments) que le code d'origine ci-dessus pour les mêmes arguments (0,012 secondes)

K (oK) , 14 octets

Solution:

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

Essayez-le en ligne!

Exemple:

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

Explication:

Prend 3 entrées implicites par spécification:

• x, nombre de nombres dans l'ensemble de sortie,
• y, limite inférieure (inclus)
• z, limite supérieure (inclus)

{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

Remarques:

Également un polyglotte q/kdb+avec un jeu supplémentaire de crochets: {y+((-)x)?1+z-y}(16 octets).

Axiom + sa bibliothèque

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 fonction f () ci-dessus renvoie comme erreur la liste vide, dans le cas f (n, a, b) avec a> b. Dans d'autres cas d'entrée non valide, il ne s'exécute pas avec un seul message d'erreur dans la fenêtre Axiom, car l'argument ne sera pas du bon type. Exemples

(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