Générer des permutations aléatoires de longueur fixe d'une chaîne

Question

Disons que mon alphabet contient X lettres et que ma langue ne supporte que les lettres Y (Y < X bien entendu). J'ai besoin de générer tous les mots possibles dans un ordre aléatoire.

E.g. Alphabet = a, b, c, d, e, f, g Y = 3

Ainsi, les mots serait: aaa aac aab aba .. bbb ccc .. (ce qui précède doit être généré dans un ordre aléatoire)

La manière triviale de le faire serait de générer les mots, puis randomiser la liste. Je ne veux pas faire ça. Je veux générer les mots dans un ordre aléatoire. Rondom (n) = lettre [x] .random (n-1) ne fonctionnera pas car alors vous aurez une liste de mots commençant par la lettre [x] .. ce qui rendra la liste pas si aléatoire.

Tout code/pseudocode apprécié.

Answer 1

Je pense que vous pouvez faire quelque chose assez simple en générant un réseau aléatoire de caractères basés sur l'alphabet que vous avez (en C#):

 char[] alphabet = {'a', 'b', 'c', 'd'}; 
     int wordLength = 3; 

     Random rand = new Random(); 

     for (int i = 0; i < 5; i++) 
     { 
      char[] word = new char[wordLength]; 
      for (int j = 0; j < wordLength; j++) 
      { 
       word[j] = alphabet[rand.Next(alphabet.Length)]; 
      } 
      Console.WriteLine(new string(word)); 
     } 

Il est évident que cela pourrait générer des doublons, mais vous pourriez peut-être stocker les résultats dans un hashmap ou quelque chose à vérifier pour les doublons si vous devez.

Answer 2

Donc, je prends ce que vous voulez est de produire une permutation de l'ensemble en utilisant le moins de mémoire possible.

Tout d'abord, cela ne peut pas être fait sans mémoire. Pour votre première chaîne, vous voulez une fonction qui pourrait produire l'une des chaînes avec une probabilité égale. Dites que cette fonction s'appelle nextString(). Si vous appelez à nouveau nextString() sans rien modifier dans l'état, bien sûr, il sera à nouveau capable de produire n'importe laquelle des chaînes.

Vous avez donc besoin de stocker quelque chose. La question est, qu'est-ce que vous avez besoin de stocker, et combien d'espace cela prendra-t-il?

Les chaînes peuvent être vues comme des nombres 0 - X^Y. (aaa = 0, aab = 1, aac = 2 ... aba = X ...) Donc, pour stocker une seule chaîne aussi efficacement que possible, vous auriez besoin de lg (X^Y) bits. Disons X = 16 et Y = 2. Ensuite, vous aurez besoin d'un octet de stockage pour spécifier une chaîne de façon unique.

Bien sûr, l'algorithme le plus naïf est de marquer chaque chaîne comme elle est produite, ce qui prend X^Y bits, qui dans mon exemple est de 256 bits (32 octets). C'est ce que vous avez dit que vous ne voulez pas faire. Vous pouvez utiliser un algorithme shuffle comme indiqué dans cette question: Creating a random ordered list from an ordered list (vous n'aurez pas besoin de stocker les chaînes comme vous les avez produites dans l'algorithme shuffle, mais vous devez les marquer). Ok, maintenant la question est, pouvons-nous faire mieux que cela? Combien avons-nous besoin de stocker, total?

Eh bien, au premier appel, nous n'avons pas besoin de stockage. Au deuxième appel, nous devons savoir lequel a été produit auparavant. Lors du dernier appel, nous avons seulement besoin de savoir lequel est le dernier. Donc, le pire est quand nous sommes à mi-chemin. Quand nous sommes à mi-chemin, il y a eu 128 chaînes produites, et il y en a 128 à faire. Nous devons savoir ce qu'il reste à produire. En supposant que le processus est vraiment aléatoire, toute scission est possible. Il y a (256 choisir 128) possibilités.Afin de potentiellement pouvoir stocker l'un de ceux-ci, nous avons besoin de lg (256 choisir 128) bits, qui selon google calculator est 251.67. Donc, si vous étiez vraiment intelligent, vous pourriez serrer l'information en 4 bits de moins que l'algorithme naïf. Probablement pas la peine.

Si vous voulez juste regarder randomish avec très peu de stockage, voir cette question: Looking for an algorithm to spit out a sequence of numbers in a (pseudo) random order

Answer 3

Comme d'autres réponses ont laissé entendre, il y a deux approches principales: 1) suivre ce que vous avez déjà généré (les solutions proposées dans cette catégorie souffrir éventuellement de ne jamais se terminer), ou 2) suivre quelles permutations doivent encore être produites (ce qui implique que les permutations doivent être pré-générées, ce qui était spécifiquement interdit dans les exigences). Voici une autre solution dont la fin est garantie et qui ne nécessite pas de pré-génération, mais peut ne pas répondre à vos besoins de randomisation (qui sont vagues à ce stade).

Aperçu général: générer un arbre pour suivre ce qui a été généré ou ce qui reste. "sélectionner" de nouvelles permutations en parcourant des liens aléatoires dans l'arbre, élaguer l'arbre au niveau des feuilles après la génération de cette permutation pour éviter qu'elle ne soit générée à nouveau.

Sans un tableau blanc pour illustrer cela, j'espère que cette description est assez bonne pour décrire ce que je veux dire: Créer un "nœud" qui a des liens vers d'autres nœuds pour chaque lettre de l'alphabet. Cela pourrait être mis en œuvre en utilisant une carte générique des lettres de l'alphabet aux noeuds ou si votre alphabet est fixe, vous pouvez créer des références spécifiques. Le nœud représente les lettres disponibles dans l'alphabet qui peuvent être "produites" ensuite pour générer une permutation. Commencez à générer des permutations en visitant le nœud racine, en sélectionnant une lettre aléatoire parmi les lettres disponibles dans ce nœud, puis en passant cette référence au nœud suivant. A chaque traversée, une lettre est produite pour la permutation. Lorsqu'une feuille est atteinte (c'est-à-dire qu'une permutation est entièrement construite), vous devez revenir en arrière sur l'arbre pour voir si les permutations disponibles sont conservées sur les nœuds parents; sinon, le noeud parent peut être élagué. En tant que détail d'implémentation, le nœud pourrait stocker l'ensemble de lettres qui ne sont pas disponibles à produire à ce point ou l'ensemble de lettres qui sont encore disponibles pour être produites à ce moment. Afin de réduire éventuellement les besoins de stockage, vous pouvez également autoriser le nœud à stocker soit avec un drapeau indiquant ce qu'il fait, de sorte que lorsque le nœud autorise plus de la moitié de l'alphabet, il stocke les lettres produites jusqu'à présent et passe à l'utilisation des lettres reste quand il y a moins de la moitié de l'alphabet disponible. L'utilisation d'une telle arborescence limite ce qui peut être produit sans avoir à pré-générer toutes les combinaisons puisque vous n'avez pas besoin de pré-construire l'arbre entier (il peut être construit au fur et à mesure que les permutations sont générées) et vous êtes garantie de terminer en raison de la purge des nœuds (c'est-à-dire que vous ne traversez que des liens vers des nœuds lorsque c'est une combinaison autorisée pour une permutation non-produite). Je crois cependant que la randomisation de la technique est un peu étrange, et je ne pense pas que chaque combinaison ait la même probabilité d'être générée à un moment donné, bien que je n'y ai pas vraiment réfléchi. Il est également intéressant de noter que même si l'arbre complet n'est pas nécessairement généré à l'avant, les frais généraux impliqués seront probablement suffisants pour que vous puissiez mieux pré-générer toutes les permutations.