Utwórz funkcję, która wygeneruje zestaw różnych liczb losowych losowanych z zakresu. Kolejność elementów w zestawie jest nieistotna (można je nawet posortować), ale musi być możliwe, aby zawartość zestawu była inna przy każdym wywołaniu funkcji.

Funkcja otrzyma 3 parametry w dowolnej kolejności:

1. Liczba liczb w zestawie wyjściowym
2. Dolny limit (włącznie)
3. Górny limit (włącznie)

Załóżmy, że wszystkie liczby są liczbami całkowitymi z zakresu od 0 (włącznie) do 2 ³¹ (wyłącznie). Dane wyjściowe można przekazać w dowolny sposób (zapis do konsoli, jako tablica itp.)

Osądzać

Kryteria obejmują 3 R.

1. Czas działania - testowany na czterordzeniowym komputerze z systemem Windows 7 z dowolnym kompilatorem, który jest łatwo lub łatwo dostępny (w razie potrzeby podaj link)
2. Wytrzymałość - czy funkcja obsługuje przypadki narożne, czy wpadnie w nieskończoną pętlę lub wygeneruje nieprawidłowe wyniki - wyjątek lub błąd dotyczący nieprawidłowego wejścia
3. Losowość - powinna generować losowe wyniki, których nie da się łatwo przewidzieć przy losowym rozkładzie. Korzystanie z wbudowanego generatora liczb losowych jest w porządku. Ale nie powinno być żadnych oczywistych uprzedzeń ani oczywistych przewidywalnych wzorców. Musi być lepszy niż generator liczb losowych używany przez Dział Księgowości w Dilbert

Jeśli jest solidny i losowy, sprowadza się do czasu działania. Brak solidności lub losowości znacznie szkodzi jego sytuacji.

Pyton

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

Prawdopodobnie właśnie wymyśliłem pewien dobrze znany algorytm, ale pomysł polega na (koncepcyjnym) wykonaniu częściowego tasowania Fisher-Yatesa zakresu, lower..upperaby uzyskać nprefiks długości równomiernie tasowanego zakresu.

Oczywiście przechowywanie całego zakresu byłoby raczej drogie, więc przechowuję tylko lokalizacje, w których elementy zostały zamienione.

W ten sposób algorytm powinien działać dobrze zarówno w przypadku próbkowania liczb z wąskiego zakresu (np. 1000 liczb w zakresie 1..1000), jak również w przypadku próbkowania liczb z dużego zakresu .

Nie jestem pewien jakości losowości z wbudowanego generatora w Pythonie, ale stosunkowo łatwo jest zamienić dowolny generator, który może generować liczby całkowite jednolicie z pewnego zakresu.

python 2.7

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

Nie jestem pewien, na czym się opierasz, używając wbudowanych losowych metod, ale i tak już i tak. miły i krótki

edit: właśnie zauważyłem, że range () nie lubi tworzyć dużych list. powoduje błąd pamięci. zobaczę, czy jest jakiś inny sposób to zrobić ...

edit2: zakres był niewłaściwą funkcją, xrange działa. Maksymalna liczba całkowita jest w rzeczywistości 2**31-1dla Pythona

test:

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

do

Zwraca tablicę zawierającą x unikatowych losowych liczb całkowitych od min do max. (dzwoniący musi zwolnić)

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

Działa, generując x losowych liczb całkowitych w zakresie, a następnie tasując je. Dodaj seed(time)gdzieś w dzwoniącym, jeśli nie chcesz uzyskać takich samych wyników przy każdym uruchomieniu.

Rubin> = 1,8

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)

Pytanie jest nieprawidłowe. Potrzebujesz jednolitego próbkowania, czy nie? W przypadku, gdy potrzebne jest jednolite próbkowanie, mam następujący kod w R, który ma średnią złożoność O ( s log s ), gdzie s jest rozmiarem próbki.

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

Oczywiście można przepisać go w C dla lepszej wydajności. Złożoność tego algorytmu omówiono w: Rouzankin, PS; Voytishek, AV W sprawie kosztów algorytmów losowego wyboru. Metody Monte Carlo. 5 (1999), no. 1, 39–54. http://dx.doi.org/10.1515/mcma.1999.5.1.39

Możesz przejrzeć ten dokument w poszukiwaniu innego algorytmu o tej samej średniej złożoności.

Ale jeśli nie potrzebujesz jednolitego próbkowania, wymagając tylko, aby wszystkie próbkowane liczby były różne, sytuacja zmienia się drastycznie. Nie jest trudno napisać algorytm o średniej złożoności O ( s ).

Zobacz także jednolite pobieranie próbek: P. Gupta, GP Bhattacharjee. (1984) Wydajny algorytm losowego próbkowania bez zamiany. International Journal of Computer Mathematics 16: 4, strony 201-209. DOI: 10.1080 / 00207168408803438

Teuhola, J. and Nevalainen, O. 1982. Dwa wydajne algorytmy losowego próbkowania bez zamiany. / IJCM /, 11 (2): 127–140. DOI: 10.1080 / 00207168208803304

W ostatnim artykule autorzy używają tabel skrótów i twierdzą, że ich algorytmy mają złożoność O ( s ). Jest jeszcze jeden algorytm szybkiej tabeli skrótów, który wkrótce zostanie zaimplementowany w pqR (dość szybki R): https://stat.ethz.ch/pipermail/r-devel/2017-October/075012.html

APL, 18 22 bajtów

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

Deklaruje anonimową funkcję, która przyjmuje dwa argumenty ⍺i ⍵. ⍺to liczba liczb losowych, którą chcesz, ⍵to wektor zawierający dolną i górną granicę, w tej kolejności.

a?bwybiera alosowe liczby od 0 - bbez zamiany. Biorąc ⍵[1]-⍵[0], otrzymujemy rozmiar zakresu. Następnie wybieramy ⍺liczby (patrz poniżej) z tego zakresu i dodajemy dolną granicę. W C to byłoby

lower + rand() * (upper - lower)

⍺razy bez wymiany. Nawiasy nie są potrzebne, ponieważ APL działa od prawej do lewej.

Zakładając, że poprawnie zrozumiałem warunki, nie spełnia to kryteriów „odporności”, ponieważ funkcja zawiedzie, jeśli otrzyma niewłaściwe argumenty (np. Przekazanie wektora zamiast skalara as ⍺).

W przypadku, gdy ⍺jest to wektor, a nie skalar, 1↑⍺bierze pierwszy element ⍺. W przypadku skalara jest to sam skalar. W przypadku wektora jest to pierwszy element. To powinno sprawić, że funkcja spełni kryteria „niezawodności”.

Przykład:

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

skompiluj i uruchom:

scalac RandSetRunner.scala 
scala RandSetRunner 200 15 0 100

W drugim wierszu uruchomionych zostanie 200 testów z 15 wartościami od 0 do 100, ponieważ Scala tworzy szybki kod bajtowy, ale potrzebuje trochę czasu uruchamiania. Tak więc 200 zaczyna się od 15 wartości od 0 do 100 zużyłoby więcej czasu.

Próbka na jednordzeniowym 2 GHz:

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

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

Logika:

Używając wbudowanych losowych i rekurencyjnie wybierających liczb z zakresu (maks. Min), dodając min i sprawdzając, czy rozmiar zestawu jest oczekiwanym rozmiarem.

Krytyka:

• Będzie to szybkie w przypadku małych próbek o dużych zakresach, ale jeśli zadaniem jest wybranie prawie wszystkich elementów próbki (999 liczb na 1000), to wielokrotnie wybierze liczby, już znajdujące się w zestawie.
• Z tego pytania nie jestem pewien, czy muszę się zdezynfekować w przypadku niespełnionych wniosków, takich jak Weź 10 różnych liczb od 4 do 8. To doprowadzi teraz do nieskończonej pętli, ale można łatwo tego uniknąć dzięki kontroli wstępnej, którą dołączę, jeśli poprosił.

Schemat

Nie jestem pewien, dlaczego potrzebujesz 3 parametrów, ani dlaczego muszę zakładać dowolny zakres ...

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

Ten kod jest najlepszy przy pobieraniu wielu próbek z zakresu.

#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 znaków)

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

Następnie użyj f [x; y; z] jako [liczba liczb w zestawie wyjściowym; punkt początkowy; rozmiar zakresu]

np. f ​​[5; 10; 10] wygeneruje 5 różnych liczb losowych od 10 do 19 włącznie.

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

Powyższe wyniki pokazują skuteczność przy 100 000 iteracjach po wybraniu 100 liczb losowych od 1 do 10 000.

R, 31 lub 40 bajtów (w zależności od znaczenia słowa „zakres”)

Jeśli wejście ma 3 liczby, a[1], a[2], a[3]a przez „zakres” rozumiesz „ciąg liczb całkowitych od [2] do [3]”, to masz to:

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

Jeśli masz tablicę, nz której zamierzasz ponownie próbkować, ale pod ograniczeniem dolnej i górnej granicy, na przykład „ponownie próbkuj wartości danej tablicy nz zakresu a[1]...a[2]”, użyj tego:

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

Jestem dość zaskoczony, dlaczego poprzedni wynik nie został zagrany w golfa, biorąc pod uwagę wbudowaną próbkę z urządzeniami zastępczymi! Tworzymy wektor, który spełnia warunek zakresu, i ponownie próbkujemy go.

• Solidność: przypadki narożne (sekwencje o tej samej długości co zakres do próbkowania) są obsługiwane domyślnie.
• Czas działania: bardzo szybki, ponieważ jest wbudowany.
• Losowość: ziarno jest automatycznie zmieniane przy każdym wywołaniu RNG.

JavaScript (przy użyciu zewnętrznej biblioteki) (64 bajty / 104 bajty ??)

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

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

Objaśnienie kodu: Wyrażenie lambda akceptuje min, max, liczenie jako argumenty. Utwórz kolekcję o rozmiarze n i przypisz każdy element do losowej liczby spełniającej kryteria min / maks. Konwertuj na natywną tablicę JS i zwróć ją. Uruchomiłem to również na wejściu o wielkości 5.000.000, a po zastosowaniu wyraźnej transformacji nadal pokazałem 5.000.000 elementów. Jeśli zostanie uzgodnione, że nie jest to wystarczająco bezpieczna gwarancja odrębności, zaktualizuję odpowiedź

Na obrazku poniżej umieściłem pewne statystyki ...

EDYCJA: Poniższy obraz pokazuje kod / wydajność, która gwarantuje, że każdy element będzie odrębny. Jest znacznie wolniejszy (6,65 sekundy dla 50 000 elementów) w porównaniu z powyższym oryginalnym kodem dla tych samych argumentów (0,012 sekundy)

K (oK) , 14 bajtów

Rozwiązanie:

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

Wypróbuj online!

Przykład:

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

Wyjaśnienie:

Przyjmuje 3 dane niejawne na specyfikację:

• x, liczba liczb w zestawie wyjściowym,
• y, dolny limit (włącznie)
• z, górny limit (włącznie)

{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

Uwagi:

Również poliglot q/kdb+z dodatkowym zestawem nawiasów: {y+((-)x)?1+z-y}(16 bajtów).

Axiom + jego biblioteka

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

Powyższa funkcja f () zwraca jako błąd pustą listę, w przypadku f (n, a, b) z a> b. W innych przypadkach niepoprawnego wprowadzania nie uruchamia się z jednym komunikatem o błędzie w oknie Axiom, ponieważ argument nie będzie odpowiedniego typu. Przykłady

(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