Dane wejściowe: dwie liczby całkowite n i k podane w dowolnej formie dogodnej dla kodu

Wynik Losowa, nie malejąca sekwencja k liczb całkowitych, każda w zakresie od 1 do n. Próbkę należy wybrać jednolicie ze wszystkich nie malejących sekwencji k liczb całkowitych o liczbach całkowitych z zakresu od 1 do n.

Dane wyjściowe mogą być w dowolnym rozsądnym formacie, który uważasz za dogodny.

Możesz użyć dowolnego pseudolosowego generatora, który udostępnia twoja ulubiona biblioteka / język.

Możemy założyć, że liczby całkowite n, k> 0.

Przykład

Powiedz n, k = 2. Nie malejące sekwencje to

1,1
1,2
2,2

Każda sekwencja powinna mieć prawdopodobieństwo 1/3 wyjścia.

Ograniczenie

Twój kod powinien działać w nie więcej niż kilka sekund dla k = 20 i n = 100.

Co nie działa

Jeśli próbkujesz losowo każdą liczbę całkowitą z zakresu od 1 do n, a następnie sortujesz listę, nie uzyskasz jednolitego rozkładu.

faktycznie , 14 12 bajtów

Ta odpowiedź jest oparta na 05AB1E odpowiedź Emigna użytkownika i odpowiedzi na to pytanie Math.SE . Zapraszamy do gry w golfa! Wypróbuj online!

;;ra+DR╚HS♀-

Ungolfing

      Implicit input n, then k.
;;    Duplicate k twice.
r     Push range [0...k] for later.
a     Invert the stack. Stack: n, k, k, [0...k]
+DR   Push the range [1..n+k-1].
╚     Shuffle the range. Stack: shuffled_range, k, [0...k]
H     Push the first k elements of shuffled_range. Call this increasing.
S     Sort increasing so the elements are actually increasing.
♀-    Subtract each element of [0...k] from each element of increasing.
      This gives us our non-decreasing sequence.
      Implicit return.

Python, 89 bajtów

from random import*
lambda n,k:[x-i for i,x in enumerate(sorted(sample(range(1,n+k),k)))]

Generowanie sekwencji rosnącej zamiast nie malejącej byłoby proste: jest to tylko losowy podzbiór kliczb między1 in posortowany.

Ale możemy przekonwertować rosnącą sekwencję na nie malejącą, zmniejszając każdą przerwę między kolejnymi liczbami o 1. Tak więc przerwa 1 staje się przerwą 0, tworząc równe liczby. Aby to zrobić, zmniejsz inajwiększą wartość oi

r[0], r[1], ..., r[n-1]  =>  r[0]-0, r[1]-1, ..., r[n-1]-(n-1)

Aby wynik był od 1do n, dane wejściowe muszą być od 1do n+k-1. Daje to bijection między nie zmniejszającymi się sekwencjami liczb pomiędzy 1i n, do rosnących sekwencji między 1i n+k-1. Ten sam bijection stosuje się w argumencie gwiazdy i słupki do zliczania takich sekwencji.

Kod korzysta z funkcji python random.sample, która pobiera kpróbki bez zamiany z listy danych wejściowych. Sortowanie to daje rosnącą sekwencję.

05AB1E , 13 bajtów

+<L.r¹£{¹L<-Ä

Wypróbuj online!

Wyjaśnienie

+<L            # range [1 ... n+k-1]
   .r          # scramble order
     ¹£        # take k numbers
       {       # sort
        ¹L<-   # subtract from their 0-based index
            Ä  # absolute value

Python, 87 bajtów

from random import*
f=lambda n,k:k>random()*(n+k-1)and f(n,k-1)+[n]or k*[7]and f(n-1,k)

Prawdopodobieństwo uwzględnienia maksymalnej możliwej wartości njest równe k/(n+k-1). Aby go dołączyć, umieść go na końcu listy i zmniejsz pozostałe potrzebne liczby k. Aby go wykluczyć, zmniejsz górną granicę n. Następnie powtarzaj tak długo, aż nie będą już potrzebne żadne wartości ( k==0).

Wygląda na randomto, że Python nie ma wbudowanej zmiennej Bernoulliego: 1 z pewnym prawdopodobieństwem i 0 w przeciwnym razie. To sprawdza, czy przypadkowa wartość od 0 do 1 generowana przez randomspada poniżej k/(n+k-1). Pyton 2 będzie jako współczynnik podziału pływaka, tak że zamiast mnożenia przez mianownik k>random()*(n+k-1).

JavaScript (Firefox 30+), 74 bajty

(n,k,i=0,j=k)=>[for(_ of Array(q=k+n-1))if(Math.random(++i)<k/q--)i-j+k--]

Wyjaśnienie

Doskonała odpowiedź xnor na język Python zawiera bardzo dobre podsumowanie tego, jak / dlaczego technika tutaj zastosowana. Pierwszym krokiem jest utworzenie zakresu [1, 2, ..., n + k - 1] :

(n,k,i=0)=>[for(_ of Array(q=k+n-1))++i]

Następnie musimy wziąć k losowych przedmiotów z tego zakresu. Aby to zrobić, musimy wybrać każdy element z prawdopodobieństwem s / q , gdzie s jest liczbą potrzebnych elementów, a q jest liczbą elementów pozostałych w zakresie. Ponieważ używamy rozumienia tablicowego, jest to dość łatwe:

(n,k,i=0)=>[for(_ of Array(q=k+n-1))if(Math.random(++i)<k/q--)k--&&i]

To daje nam równomiernie rozmieszczoną rosnącą sekwencję liczb. Można to naprawić, odejmując liczbę znalezionych wcześniej elementów j :

(n,k,i=0,j=0)=>[for(_ of Array(q=k+n-1))if(Math.random(++i)<k/q--)k--&&i-j++]

Na koniec, przechowując k w j , możemy włączyć k--do wyrażenia i zapisać kilka bajtów:

(n,k,i=0,j=k)=>[for(_ of Array(q=k+n-1))if(Math.random(++i)<k/q--)i-j+k--]

TI-BASIC, 54 bajtów

Prompt N,K
K→dim(L1
While K
If rand<K/(N+K-1
Then
N→L1(K
K-1→K
Else
N-1→N
End
End
Disp L1

Postępuj zgodnie z logiką xnor, z niewielkim zastrzeżeniem. Możemy teoretycznie ogolić bajt, wykonując coś takiego:

K>rand(N+K-1

Ale rand (jest zarezerwowany, aby utworzyć listę liczb losowych, więc nie bylibyśmy w stanie wykonać żądanego domniemanego mnożenia, aby zapisać bajt.

To powinno działać przyzwoicie szybko na 84+ na ograniczenie, ale sprawdzę, aby się upewnić, kiedy będę mógł.

PHP, 77 75 73 bajtów

foreach(array_rand(range(2,$argv[1]+$k=$argv[2]),$k)as$v)echo$v+1-$i++,_;

Uruchom tak:

php -r 'foreach(array_rand(range(2,$argv[1]+$k=$argv[2]),$k)as$v)echo$v+1-$i++,_;' -- 10 5 2>/dev/null;echo
> 1_4_6_9_9_

Wyjaśnienie

foreach(                    # Iterate over...
  array_rand(               #   a (sorted) random number of items from...
    range(                  #     an array with items...
      2,                    #       from 2
      $argv[1]+$k=$argv[2]  #       to n + k (set arg 2 to $k)
    ),
    $k                      #     Take k number of items (their keys)
  )
  as $v
)
  echo $v +1 - $i++,"_";    # Print the value subtracted by the index.
                            # Need to add 1, because keys are 0-indexed.

Poprawki

• Zapisano 2 bajty, usuwając end()połączenie i ustawiając $argv[2]na$k aby skrócić dostęp do argumentów
• Zapisano 2 bajty, usuwając indeks z foreach, ponieważ jest to po prostu liczba rosnąca. $iZamiast tego zwiększaj każdą iterację