Wählen Sie eine zufällige, nicht abnehmende Sequenz

20

Eingabe: Zwei Ganzzahlen n und k in jeder für Ihren Code geeigneten Form

Ausgabe Eine zufällige nicht abnehmende Folge von k ganzen Zahlen im Bereich von 1 bis n. Die Stichprobe sollte einheitlich aus allen nicht abnehmenden Folgen von k ganzen Zahlen mit ganzen Zahlen im Bereich von 1 bis n ausgewählt werden.

Die Ausgabe kann in jedem vernünftigen Format erfolgen, das Sie für zweckmäßig halten.

Sie können jeden Pseudozufallsgenerator verwenden, den Ihre bevorzugte Bibliothek / Sprache bereitstellt.

Wir können annehmen, dass die ganzen Zahlen n, k> 0 sind.

Beispiel

Sagen wir n, k = 2. Die nicht abnehmenden Folgen sind

1,1
1,2
2,2

Jede Sequenz sollte eine Ausgabewahrscheinlichkeit von 1/3 haben.

Beschränkung

Ihr Code sollte für k = 20 und n = 100 nicht länger als ein paar Sekunden ausgeführt werden.

Was geht nicht

Wenn Sie einfach jede Ganzzahl zufällig aus dem Bereich von 1 bis n abtasten und dann die Liste sortieren, erhalten Sie keine gleichmäßige Verteilung.

DJMcMayhem
quelle
Die Ausgabe der Anzahl nicht abnehmender Sequenzen für n, k könnte für sich genommen eine interessante Herausforderung darstellen, wenn dies noch nicht geschehen ist ...
ETHproductions
1
@ETHproductions Nicht wirklich, es ist nur ein Binomial (im Zusammenhang damit )
Sp3000
@ Sp3000 Ah, OK. Es war eine lustige Herausforderung für mich, herauszufinden, wie man es effizient berechnet.
ETHproductions
Ihre Anforderung, dass jede Sequenz die gleiche Ausgabewahrscheinlichkeit hat, kann mit den meisten PRNGs der Gartensorte, die möglicherweise nur 32- oder 48-Bit-Zustände haben, nicht erfüllt werden. Laut Wolfram gibt es 535 Trillionen 20 Elementteilfolgen von 1, ..., 100 (nicht überprüft, wie viele davon nicht abnehmen). 2 ^ 64 ist nur 18 Billionen.
Sinan Ünür

Antworten:

1

Eigentlich , 14 12 Bytes

Diese Antwort basiert auf der 05AB1E-Antwort von Emigna und den Antworten auf diese Math.SE-Frage . Golfvorschläge willkommen! Probieren Sie es 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.
Sherlock9
quelle
13

Python, 89 Bytes

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

Es ist einfach, eine aufsteigende und keine absteigende Folge zu erzeugen: Dies ist nur eine zufällige Teilmenge von kZahlen zwischen 1und n, sortiert.

Wir können jedoch eine aufsteigende Folge in eine nicht absteigende umwandeln, indem wir jede Lücke zwischen aufeinanderfolgenden Zahlen um 1 verkleinern. Eine Lücke von 1 wird also zu einer Lücke von 0, was gleiche Zahlen ergibt. Verringern Sie dazu den i'größten Wert umi

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

Damit das Ergebnis von 1bis ist n, muss die Eingabe von 1bis sein n+k-1. Dies ergibt einen Unterschied zwischen nicht abnehmenden Zahlenfolgen zwischen 1und nund zunehmenden Folgen zwischen 1und n+k-1. Dieselbe Bijektion wird im Argument mit den Sternen und Balken zum Zählen solcher Sequenzen verwendet.

Der Code verwendet die Python-Funktion random.sample, die kersatzlose Samples aus der Eingabeliste entnimmt . Sortieren ergibt die aufsteigende Reihenfolge.

xnor
quelle
Das ist beeindruckend. Könnten Sie bitte eine Erklärung der Methode hinzufügen?
Yup, beschäftigt jetzt, wird später erklären.
xnor
Ich habe 90 Bytes gezählt ... (und Sie können auch import*1 Byte speichern)
Rod
@ Rod Danke, das habe ich vergessen.
xnor
7

05AB1E , 13 Bytes

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

Probieren Sie es online!

Erläuterung

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

Python, 87 Bytes

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)

Die Wahrscheinlichkeit, dass der maximal mögliche Wert nenthalten ist, ist gleich k/(n+k-1). Um es einzuschließen, setzen Sie es an das Ende der Liste und dekrementieren Sie die verbleibenden Zahlen k. Um dies auszuschließen, dekrementieren Sie die Obergrenze n. Dann wiederholen, bis keine Werte mehr benötigt werden ( k==0).

Pythons randomscheint keine eingebaute Bernoulli-Variable zu haben: 1 mit einer gewissen Wahrscheinlichkeit und 0 mit einer anderen Wahrscheinlichkeit. Dies prüft also, ob ein durch erzeugter Zufallswert zwischen 0 und 1 randomunterschritten wird k/(n+k-1). Python 2 würde das Verhältnis als float Teilung, so dass wir stattdessen mehrfach durch den Nenner: k>random()*(n+k-1).

xnor
quelle
Würde Numpy hier helfen?
@Lembik Gut gedacht, aber es sieht so aus, als müsste man importieren numpy.random, was zu lang ist.
xnor
5

JavaScript (Firefox 30+), 74 Byte

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

Erläuterung

xnors ausgezeichnete Python-Antwort enthält eine sehr gute Zusammenfassung, wie / warum die hier verwendete Technik funktioniert. Der erste Schritt besteht darin, den Bereich [1, 2, ..., n + k - 1] zu erstellen :

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

Als nächstes müssen wir k zufällige Gegenstände aus diesem Bereich nehmen. Dazu müssen wir jeden Artikel mit der Wahrscheinlichkeit s / q auswählen , wobei s die Anzahl der noch benötigten Artikel und q die Anzahl der im Bereich verbleibenden Artikel ist. Da wir ein Array-Verständnis verwenden, ist dies ziemlich einfach:

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

Dies gibt uns eine gleichmäßig verteilte, zunehmende Folge von Zahlen. Dies kann durch Subtrahieren der Anzahl der zuvor gefundenen Elemente j behoben werden :

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

Schließlich durch Speichern von k in können wir jk-- in den Ausdruck einbauen und ein paar Bytes sparen:

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

TI-BASIC, 54 Bytes

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

Folgen Sie der Logik von xnor mit einer kleinen Einschränkung. Wir könnten ein Byte theoretisch so rasieren:

K>rand(N+K-1

Aber rand (ist reserviert, um eine Liste von Zufallszahlen zu erstellen, sodass wir nicht in der Lage wären, die gewünschte implizite Multiplikation durchzuführen, um ein Byte zu speichern.

Dies sollte mit 84+ pro Einschränkung anständig schnell gehen, aber ich werde überprüfen, ob ich es kann.

TiKevin83
quelle
1

PHP, 77 75 73 Bytes

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

Laufen Sie wie folgt:

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_

Erläuterung

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.

Optimierungen

  • 2 Bytes durch Entfernen des end()Anrufs und Festlegen gespeichert$argv[2] zu , $kanstatt zu shorten Zugriff auf Argumente
  • Durch Entfernen des Index aus foreach wurden 2 Byte gespart, da es sich lediglich um eine inkrementelle Zahl handelt. Einfach inkrementieren$iErhöhe stattdessen jede Iteration
aross
quelle
Zuerst JavaScript und jetzt PHP. Alle besten wissenschaftlichen Programmiersprachen :) Danke.
@ Lembik, bitte schön. Allerdings wird ein grundlegendes PRNG verwendet. Nicht für kryptografische Zwecke verwenden . :)
Am