Gibt es einen Satz, der die Berechnung der Gesamtzahl eines kombinatorischen Gegenstands bezieht, indem er zufällig eins abholt?

Question

Eine gemeinsame algorithmische Herausforderung besteht darin, ein Objekt einer bestimmten Art, gleichmäßig zufällig zu erzeugen. Zum Beispiel erstellen Sie beispielsweise eine zufällige Permutation der Größe $ K $ aus einem bestimmten (multi) Satz von $ n $ Charaktere, wie in Diese Frage .

Ich habe bemerkt, dass bei der Lösung solcher Aufgaben jeder Algorithmus für berechnet, die Anzahl solcher

Beispielsweise, Angenommen, ich möchte eine zufällige Folge von $ N $ $ 1 erstellen $ S und $ 0 $ s, wo keine zwei benachbarten $ 1 $ S vorhanden sind. Ich kann beginnen, indem ich $ a [n] $ die Anzahl solcher Sequenzen sei, und beobachten Sie das $$ a [n]= a [n-1] + a [n-2]. $$

(Dies ist die Fibonacci-Beziehung.) Dies ermöglicht es mir, eine Tabelle von $ A [i] $ für $ i= 1 $ in effizient zu berechnen $ i= n $ . Wenn ich jetzt eine zufällige solche Reihenfolge generieren möchte, ist alles, was ich tun muss, ist:

Schritt 1: einen zufälligen Wert erzeugen $ r $ aus $ 1 $ auf $ A [n] $ .

Schritt 2: Verwenden Sie die Rezidivbeziehung, um einen Unterlauf zu lokalisieren, der dem $ R $ der Sequenz entspricht: .

• wenn $ r \ le a [n-1] $ , rekursiv den $ r $ te Sequenz, gezählt von $ A [N-1] $ , und hängen Sie einen $ 0 $ an.

• ansonsten, wenn $ a [n-1] , eingestellt $ R '= R - A [N-1] $ , und rekursiv finden Sie den $ r' $ Die Sequenz, gezählt von $ A [N-2] $ , und hängen Sie einen $ 01 $ an.

, was hier eingeschaltet ist, ist, dass er angesichts einer Wiederholungsbeziehung für $ A [n] $ , kann ich dies in einen rekursiven Algorithmus umwandeln, der die zurückgibt $ R $ tiges Objekt, das von $ A [N] $ gezählt wird. Ich gehe davon aus, dass dies bekannt ist, also würde ich mich für weitere Referenzen oder klassische Ergebnisse interessieren. Insbesondere ist dies nicht nur für das Beispiel $ A [N] $ ,, sollte jedoch treu sein, um eine beliebige -Rezidivierungsbeziehung zu erfüllen Eigenschaften.

Ich denke auch, dass dies mit einigen Forschungen zu zufälligen Tests zusammenhängt.

Answer 1

Diese sind bekannt als Ranking- und Ranking-Funktionen .Sie haben Recht auf der Korrespondenz zwischen Rezidivierungsbeziehungen zum Zählen und amerikanischen Algorithmen.