Erstellen Sie eine Funktion, die eine Reihe unterschiedlicher Zufallszahlen aus einem Bereich ausgibt. Die Reihenfolge der Elemente in der Menge ist unwichtig (sie können sogar sortiert werden), aber es muss möglich sein, dass der Inhalt der Menge bei jedem Aufruf der Funktion unterschiedlich ist.

Die Funktion erhält 3 Parameter in beliebiger Reihenfolge:

1. Anzahl der Zahlen im Ausgabesatz
2. Untergrenze (einschließlich)
3. Obergrenze (einschließlich)

Angenommen, alle Zahlen sind Ganzzahlen im Bereich von 0 (einschließlich) bis 2 ³¹ (exklusiv). Die Ausgabe kann beliebig zurückgegeben werden (Schreiben an die Konsole, als Array usw.)

Richten

Kriterien sind die 3 Rs

1. Laufzeit - getestet auf einem Quad-Core-Windows 7-Computer mit einem beliebigen Compiler, der frei oder leicht verfügbar ist (ggf. einen Link bereitstellen)
2. Robustheit - Behandelt die Funktion Eckfälle oder fällt sie in eine Endlosschleife oder führt zu ungültigen Ergebnissen - eine Ausnahme oder ein Fehler bei ungültiger Eingabe ist gültig
3. Zufälligkeit - Es sollten zufällige Ergebnisse erzielt werden, die mit einer zufälligen Verteilung nicht leicht vorhersehbar sind. Die Verwendung des eingebauten Zufallszahlengenerators ist in Ordnung. Es sollte jedoch keine offensichtlichen Vorurteile oder offensichtlichen vorhersehbaren Muster geben. Muss besser sein als der Zufallszahlengenerator, der von der Buchhaltungsabteilung in Dilbert verwendet wird

Wenn es robust und zufällig ist, kommt es auf die Laufzeit an. Wenn sie nicht robust oder zufällig sind, schadet dies ihrer Position erheblich.

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

Ich habe wahrscheinlich gerade einen bekannten Algorithmus neu erfunden, aber die Idee ist, (konzeptionell) ein partielles Fisher-Yates-Shuffle des Bereichs durchzuführen lower..upper, um das Längenpräfix neines gleichmäßig gemischten Bereichs zu erhalten.

Das Speichern des gesamten Sortiments wäre natürlich ziemlich teuer, daher speichere ich nur die Orte, an denen die Elemente ausgetauscht wurden.

Auf diese Weise sollte der Algorithmus sowohl in dem Fall, in dem Sie Zahlen aus einem engen Bereich abtasten (z. B. 1000 Zahlen im Bereich 1..1000), als auch in dem Fall, in dem Sie Zahlen aus einem großen Bereich abtasten, eine gute Leistung erbringen .

Ich bin mir nicht sicher über die Qualität der Zufälligkeit des in Python integrierten Generators, aber es ist relativ einfach, einen Generator auszutauschen, der aus einem bestimmten Bereich einheitliche Ganzzahlen erzeugen kann.

Python 2.7

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

Ich bin mir nicht sicher, worauf du stehst, wenn du eingebaute Zufallsmethoden verwendest, aber hier geht es trotzdem. nett und kurz

edit: habe gerade bemerkt, dass range () keine großen Listen erstellt. führt zu einem Speicherfehler. werde sehen, ob es einen anderen Weg gibt, dies zu tun ...

edit2: range war die falsche funktion, xrange funktioniert. Die maximale Ganzzahl ist eigentlich 2**31-1für Python

Prüfung:

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

C.

Gibt ein Array zurück, das x eindeutige zufällige Ints zwischen min und max enthält. (Anrufer muss frei sein)

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

Funktioniert, indem x aufeinanderfolgende zufällige Ganzzahlen im Bereich generiert und dann gemischt werden. Fügen Sie seed(time)irgendwo im Anrufer eine hinzu, wenn Sie nicht bei jedem Lauf die gleichen Ergebnisse erzielen möchten.

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)

Die Frage ist nicht richtig. Benötigen Sie eine einheitliche Probenahme oder nicht? Für den Fall, dass eine einheitliche Stichprobe erforderlich ist, habe ich den folgenden Code in R, der die durchschnittliche Komplexität O ( s log s ) aufweist, wobei s die Stichprobengröße ist.

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

Natürlich kann man es für eine bessere Leistung in C umschreiben. Die Komplexität dieses Algorithmus wird diskutiert in: Rouzankin, PS; Voytishek, AV Über die Kosten von Algorithmen für die zufällige Auswahl. Monte-Carlo-Methoden Appl. 5 (1999), no. 1, 39-54. http://dx.doi.org/10.1515/mcma.1999.5.1.39

In diesem Artikel können Sie nach einem anderen Algorithmus mit derselben durchschnittlichen Komplexität suchen.

Wenn Sie jedoch keine einheitliche Stichprobe benötigen und nur alle Stichprobenzahlen unterschiedlich sein müssen, ändert sich die Situation dramatisch. Es ist nicht schwer, einen Algorithmus mit durchschnittlicher Komplexität O ( s ) zu schreiben .

Siehe auch für eine einheitliche Stichprobe: P. Gupta, GP Bhattacharjee. (1984) Ein effizienter Algorithmus für die ersatzlose Zufallsauswahl. Internationales Journal für Computermathematik 16: 4, Seiten 201-209. DOI: 10.1080 / 00207168408803438

Teuhola, J. und Nevalainen, O. 1982. Zwei effiziente Algorithmen für die ersatzlose Zufallsauswahl. / IJCM /, 11 (2): 127–140. DOI: 10.1080 / 00207168208803304

Im letzten Artikel verwenden die Autoren Hash-Tabellen und behaupten, dass ihre Algorithmen O ( s ) -Komplexität haben. Es gibt einen weiteren schnellen Hash-Tabellen-Algorithmus, der in Kürze in pqR (ziemlich schnelles R) implementiert wird: https://stat.ethz.ch/pipermail/r-devel/2017-October/075012.html

APL, 18 22 Bytes

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

Deklariert eine anonyme Funktion, die zwei Argumente ⍺und akzeptiert ⍵. ⍺ist die Anzahl der gewünschten Zufallszahlen, ⍵ist ein Vektor, der die unteren und oberen Grenzen in dieser Reihenfolge enthält.

a?bwählt ersatzlos aZufallszahlen zwischen 0 und b0 aus. Durch die Aufnahme erhalten ⍵[1]-⍵[0]wir die Bereichsgröße. Dann wählen wir ⍺Zahlen (siehe unten) aus diesem Bereich und fügen die Untergrenze hinzu. In C wäre dies

lower + rand() * (upper - lower)

⍺mal ersatzlos. Klammern werden nicht benötigt, da APL von rechts nach links arbeitet.

Vorausgesetzt, ich habe die Bedingungen richtig verstanden, verfehlt dies die Kriterien für die Robustheit, da die Funktion fehlschlägt, wenn falsche Argumente angegeben werden (z. B. Übergabe eines Vektors anstelle eines Skalars als ⍺).

Für den Fall, dass ⍺es sich eher um einen Vektor als um einen Skalar handelt, 1↑⍺wird das erste Element von übernommen ⍺. Für einen Skalar ist dies der Skalar selbst. Für einen Vektor ist es das erste Element. Dadurch sollte die Funktion die Robustheitskriterien erfüllen.

Beispiel:

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

kompilieren und ausführen:

scalac RandSetRunner.scala 
scala RandSetRunner 200 15 0 100

In der zweiten Zeile werden 200 Tests mit 15 Werten von 0 bis 100 ausgeführt, da Scala einen schnellen Bytecode erzeugt, jedoch einige Startzeit benötigt. 200 Starts mit 15 Werten von 0 bis 100 würden also mehr Zeit in Anspruch nehmen.

Probe auf einem 2 GHz Single Core:

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

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

Logik:

Verwenden Sie die eingebauten zufälligen und rekursiv ausgewählten Zahlen im Bereich (max-min), fügen Sie min hinzu und prüfen Sie, ob die Größe des Satzes der erwarteten Größe entspricht.

Kritik:

• Es ist schnell für kleine Stichproben mit großen Bereichen, aber wenn die Aufgabe darin besteht, fast alle Elemente einer Stichprobe auszuwählen (999 von 1000 Zahlen), werden wiederholt Zahlen ausgewählt, die bereits im Satz enthalten sind.
• Bei der Frage bin ich mir nicht sicher, ob ich mich gegen nicht erfüllbare Anfragen wie Take 10 verschiedene Zahlen von 4 bis 8 bereinigen muss. Dies führt nun zu einer Endlosschleife, kann aber mit einer vorherigen Prüfung, die ich anhängen werde, leicht vermieden werden angefordert.

Planen

Ich bin mir nicht sicher, warum 3 Parameter übergeben werden müssen oder warum ich einen Bereich annehmen muss ...

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

Dieser Code eignet sich am besten zum Zeichnen vieler Proben aus dem Bereich.

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

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

Verwenden Sie dann f [x; y; z] als [Anzahl der Zahlen im Ausgabesatz; Startpunkt; Größe des Bereichs]

Beispiel: f [5; 10; 10] gibt 5 verschiedene Zufallszahlen zwischen 10 und einschließlich 19 aus.

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

Die obigen Ergebnisse zeigen die Leistung bei 100.000 Iterationen der Auswahl von 100 Zufallszahlen zwischen 1 und 10.000.

R, 31 oder 40 Bytes (abhängig von der Bedeutung des Wortes "Bereich")

Wenn der Eingang 3 Zahlen hat a[1], a[2], a[3]und mit "Bereich" "eine ganzzahlige Folge von [2] bis [3]" gemeint ist, haben Sie Folgendes:

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

Wenn Sie ein Array haben, nvon dem Sie ein Resample durchführen möchten, das jedoch unter der Einschränkung der unteren und oberen Grenzen steht, z. B. "Resample-Werte des angegebenen Arrays naus dem Bereich a[1]...a[2]", verwenden Sie Folgendes :

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

Ich bin ziemlich überrascht, warum das vorherige Ergebnis angesichts der eingebauten Probe mit Ersatzeinrichtungen nicht Golf gespielt wurde! Wir erstellen einen Vektor, der die Bereichsbedingung erfüllt, und tasten ihn erneut ab.

• Robustheit: Die Eckfälle (Sequenzen mit der gleichen Länge wie der Bereich, aus dem abgetastet werden soll) werden standardmäßig behandelt.
• Laufzeit: extrem schnell, weil es eingebaut ist.
• Zufälligkeit: Der Startwert wird bei jedem Aufruf des RNG automatisch geändert.

Javascript (mit externer Bibliothek) (64 Bytes / 104 Bytes ??)

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

Link zur Bibliothek: https://github.com/mvegh1/Enumerable/

Code-Erklärung: Der Lambda-Ausdruck akzeptiert min, max und zählt als Argumente. Erstellen Sie eine Sammlung der Größe n und ordnen Sie jedes Element einer Zufallszahl zu, die den Min / Max-Kriterien entspricht. In ein natives JS-Array konvertieren und zurückgeben. Ich habe dies auch mit einer Eingabe der Größe 5.000.000 ausgeführt und nach dem Anwenden einer bestimmten Transformation immer noch 5.000.000 Elemente angezeigt. Wenn vereinbart wird, dass dies nicht sicher genug ist, um die Unterscheidbarkeit zu gewährleisten, werde ich die Antwort aktualisieren

Ich habe einige Statistiken in das Bild unten aufgenommen ...

BEARBEITEN: Das folgende Bild zeigt Code / Leistung, die garantiert, dass jedes Element anders ist. Es ist viel viel langsamer (6,65 Sekunden für 50.000 Elemente) als der ursprüngliche Code oben für dieselben Argumente (0,012 Sekunden).

K (oK) , 14 Bytes

Lösung:

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

Probieren Sie es online aus!

Beispiel:

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

Erläuterung:

Nimmt 3 implizite Eingaben pro Spezifikation vor:

• x, Anzahl der Zahlen im Ausgabesatz,
• y, untere Grenze (einschließlich)
• z, Obergrenze (einschließlich)

{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

Anmerkungen:

Auch ein Polyglot in q/kdb+mit einem zusätzlichen Satz von Klammern: {y+((-)x)?1+z-y}(16 Bytes).

Axiom + seine Bibliothek

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

Die obige Funktion f () gibt als Fehler die leere Liste zurück, im Fall f (n, a, b) mit a> b. In anderen Fällen ungültiger Eingaben wird es nicht mit einer Fehlermeldung im Axiom-Fenster ausgeführt, da das Argument nicht vom richtigen Typ ist. Beispiele

(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