Erweitern Sie einen Zufallsbereich von 1-5 auf 1-7

Question

Geben Sie eine Funktion an, die eine zufällige ganze Zahl im Bereich von 1 bis 5 erzeugt. Schreiben Sie eine Funktion, die eine zufällige ganze Zahl im Bereich von 1 bis 7 erzeugt.

1. Was ist eine einfache Lösung?
2. Was ist eine effektive Lösung, um die Speichernutzung zu reduzieren oder mit einer langsameren CPU zu arbeiten?

Answer 1

Ich weiß, dass diese Frage bereits beantwortet wurde, aber sie scheint gut zu funktionieren, aber ich kann Ihnen nicht sagen, ob es eine Verzerrung gibt. Meine "Tests" legen nahe, dass es zumindest vernünftig ist.

Vielleicht wäre Adam Rosenfield so freundlich, sich dazu zu äußern?

Meine (naive?) Idee ist folgende:

Akkumulieren Sie rand5, bis genügend Zufallsbits vorhanden sind, um einen rand7 zu bilden. Dazu braucht man höchstens 2 rand5. Um die Zahl rand7 zu erhalten, verwende ich den akkumulierten Wert mod 7.

Um zu vermeiden, dass der Akkumulator überläuft, und da der Akkumulator mod 7 ist, nehme ich den mod 7 des Akkumulators:

(5a + rand5) % 7 = (k*7 + (5a%7) + rand5) % 7 = ( (5a%7) + rand5) % 7

Es folgt die Funktion rand7():

(Ich habe den Bereich von rand5 auf 0-4 gesetzt und rand7 ist ebenfalls 0-6).

int rand7(){
  static int    a=0;
  static int    e=0;
  int       r;
  a = a * 5 + rand5();
  e = e + 5;        // added 5/7ths of a rand7 number
  if ( e<7 ){
    a = a * 5 + rand5();
    e = e + 5;  // another 5/7ths
  }
  r = a % 7;
  e = e - 7;        // removed a rand7 number
  a = a % 7;
  return r;
}

Edit: Ergebnisse für 100 Millionen Versuche hinzugefügt.

Real'-Randfunktionen mod 5 oder 7

rand5 : avg=1.999802 0:20003944 1:19999889 2:20003690 3:19996938 4:19995539 rand7 : avg=3.000111 0:14282851 1:14282879 2:14284554 3:14288546 4:14292388 5:14288736 6:14280046

Mein Rand7

Der Durchschnitt sieht gut aus, und auch die Zahlenverteilungen sehen gut aus.

randt : avg=3.000080 0:14288793 1:14280135 2:14287848 3:14285277 4:14286341 5:14278663 6:14292943

Answer 2

Hier ist eine Lösung, die vollständig mit ganzen Zahlen auskommt und nur etwa 4 % vom Optimum entfernt ist (d. h. sie verwendet 1,26 Zufallszahlen in {0..4} für jede in {0..6}). Der Code ist in Scala, aber die Mathematik sollte in jeder Sprache einigermaßen klar sein: Man macht sich die Tatsache zunutze, dass 7^9 + 7^8 sehr nahe an 5^11 liegt. Man wählt also eine 11-stellige Zahl zur Basis 5 und interpretiert sie dann als 9-stellige Zahl zur Basis 7, wenn sie im Bereich liegt (was 9 Zahlen zur Basis 7 ergibt), oder als 8-stellige Zahl, wenn sie über der 9-stelligen Zahl liegt, usw.:

abstract class RNG {
  def apply(): Int
}

class Random5 extends RNG {
  val rng = new scala.util.Random
  var count = 0
  def apply() = { count += 1 ; rng.nextInt(5) }
}

class FiveSevener(five: RNG) {
  val sevens = new Array[Int](9)
  var nsevens = 0
  val to9 = 40353607;
  val to8 = 5764801;
  val to7 = 823543;
  def loadSevens(value: Int, count: Int) {
    nsevens = 0;
    var remaining = value;
    while (nsevens < count) {
      sevens(nsevens) = remaining % 7
      remaining /= 7
      nsevens += 1
    }
  }
  def loadSevens {
    var fivepow11 = 0;
    var i=0
    while (i<11) { i+=1 ; fivepow11 = five() + fivepow11*5 }
    if (fivepow11 < to9) { loadSevens(fivepow11 , 9) ; return }
    fivepow11 -= to9
    if (fivepow11 < to8) { loadSevens(fivepow11 , 8) ; return }
    fivepow11 -= to8
    if (fivepow11 < 3*to7) loadSevens(fivepow11 % to7 , 7)
    else loadSevens
  }
  def apply() = {
    if (nsevens==0) loadSevens
    nsevens -= 1
    sevens(nsevens)
  }
}

Wenn Sie einen Test in den Interpreter (eigentlich REPL) einfügen, erhalten Sie:

scala> val five = new Random5
five: Random5 = Random5@e9c592

scala> val seven = new FiveSevener(five)
seven: FiveSevener = FiveSevener@143c423

scala> val counts = new Array[Int](7)
counts: Array[Int] = Array(0, 0, 0, 0, 0, 0, 0)

scala> var i=0 ; while (i < 100000000) { counts( seven() ) += 1 ; i += 1 }
i: Int = 100000000

scala> counts
res0: Array[Int] = Array(14280662, 14293012, 14281286, 14284836, 14287188,
14289332, 14283684)

scala> five.count
res1: Int = 125902876

Die Verteilung ist schön flach (innerhalb von etwa 10k von 1/7 von 10^8 in jedem Bin, wie von einer annähernd Gaußschen Verteilung erwartet).

Answer 3

Das war's. Gleichmäßige Verteilung und keine rand5-Aufrufe.

def rand7:
    seed += 1
    if seed >= 7:
        seed = 0
    yield seed

Das Saatgut muss vorher gesetzt werden.

Answer 4

Es gibt elegante Algorithmen, die oben zitiert wurden, aber hier ist eine Möglichkeit, sich dem zu nähern, auch wenn es ein Umweg sein mag. Ich gehe von Werten aus, die von 0.

R2 = Zufallszahlengenerator, der Werte kleiner als 2 liefert (Stichprobenraum = {0, 1})
R8 = Zufallszahlengenerator, der Werte kleiner als 8 liefert (Stichprobenraum = {0, 1, 2, 3, 4, 5, 6, 7})

Um R8 aus R2 zu generieren, führen Sie R2 dreimal aus und verwenden das kombinierte Ergebnis aller drei Durchläufe als eine dreistellige Binärzahl. Hier ist der Wertebereich, wenn R2 dreimal ausgeführt wird:

0 0 0 --> 0
.
.
1 1 1 --> 7

Um nun R7 aus R8 zu erzeugen, führen wir einfach R7 erneut aus, wenn es 7 ergibt:

int R7() {
  do {
    x = R8();
  } while (x > 6)
  return x;
}

Die Umgehungslösung besteht darin, R2 aus R5 zu generieren (so wie wir R7 aus R8 generiert haben), dann R8 aus R2 und dann R7 aus R8.

Answer 5

In php

function rand1to7() {
    do {
        $output_value = 0;
        for ($i = 0; $i < 28; $i++) {
            $output_value += rand1to5();
        }
    while ($output_value != 140);
    $output_value -= 12;
    return floor($output_value / 16);
}

Schleifen, um eine Zufallszahl zwischen 16 und 127 zu erzeugen, dividiert durch sechzehn, um eine Fließkommazahl zwischen 1 und 7,9375 zu erzeugen, und rundet dann ab, um eine int-Zahl zwischen 1 und 7 zu erhalten. Wenn ich mich nicht irre, gibt es eine Chance von 16/112, eines der 7 Ergebnisse zu erhalten.