Y a-t-il un théorème qui raconte le calcul du nombre total d'un objet combinatoire avec la cueillette au hasard?

Question

Un défi algorithmique commun consiste à générer un objet d'un certain type, uniformément au hasard. Par exemple, générer une permutation aléatoire de taille $ k $ à partir d'un ensemble donné (multi) de $ n $ Personnages, comme dans Cette question .

J'ai remarqué que lors de la résolution de telles tâches, tout algorithme pour calculer le nombre d'objets combinatoires via une relation de récurrence peut être transformé en algorithme sur générer telle objets combinatoires. Ma question est: y a-t-il un nom pour cette technique? Y a-t-il un théorème qui dit quand c'est vrai?

par exemple, supposons générer une séquence aléatoire de $ n $ $ 1 $ s et $ 0 $ s, où il n'y a pas deux adjacents $ 1 $ s. Je peux commencer en laissant $ a [n] $ être le nombre de telles séquences et observer que $$ A [N]= A [N-1] + A [N-2]. $$

(C'est la relation Fibonacci.) Cela me permet de calculer efficacement une table de $ a [i] $ pour $ i= 1 $ à $ i= n $ . Maintenant, si je veux générer une séquence aléatoire de cette séquence, tout ce que je dois faire est de:

Étape 1: générer une valeur aléatoire $ r $ de $ 1 $ à $ a [n] $ .

Étape 2: Utilisez la relation de récurrence pour localiser un sous-tracé qui correspond à la $ R $ TH Séquence:

• si $ r \ le a [n-1] $ , trouvez de manière récursive la $ r $ < / SPAN> TH Séquence comptée par $ A [N-1] $ et Ajoutez une $ 0 $ .

• sinon, si $ a [n-1] , défini $ R '= R - A [N-1] $ et trouvez récursivement la $ R' $ ème séquence comptée par $ A [n-2] $ et ajoute une 01 $

Qu'est-ce qui semble aller ici est que, étant donné une relation de récurrence pour $ a [n] $ , je peux transformer cela en un algorithme récursif qui retourne la $ R $ thy objet compté par $ a [n] $ . Je suppose que cela est bien connu, alors je serais intéressé par des références ou des résultats classiques à ce sujet. En particulier, ce n'est pas simplement spécifique à l'exemple $ a [n] $ , mais devrait être vrai pour toute relation de récurrence satisfaisante Propriétés.

En outre, je pense que cela peut être lié à certaines recherches sur des tests aléatoires.

Answer 1

Ceux-ci sont connus sous le nom de Fonctions de classement et irréligibles .Vous avez raison sur la correspondance entre les relations de récurrence pour les algorithmes de comptage et non irréparable.