Discussion :

[BBouille]

Bonjour les amis,
J'ai commencé un truc mais j'ai interrompu mon programme quand j'ai vu que je ne pouvais plus ouvrir le fichier de sauvegarde des données en cours.
Voilà l'énoncé : on tire 5 lettres dans un sac de 100 lettres. Pour ceux qui ont reconnu le sac, c'est un sac de Scrabble.
Combien de groupes de 5 lettres peut-on tirer?
J'ai donc imbriqué 5 boucles de 1 à 100 en enregistrant les 5 lettres à chaque itération et en écartant les cas où les indices des boucles sont identiques.
Je sais que ce ne doit pas être 5x100 mais plutôt 100x99x98x97x96 mais comment être sûr qu'on ne loupe aucune combinaison?
Comme certaines lettres sont multiples je comptais supprimer les doublons après le premier traitement.
Mais comme je ne vois déjà pas comment faire le premier traitement je me suis arrêté là.
Quelqu'un aurait-il une idée, un moyen, un algorithme pour faire ça?
Merci à vous.

[valentin03]

Bonjour, je peux te proposer ça (c'est un Basic):
n = 100 dans ton cas
Les lettres sont dans a$ (qui est une chaine)
#w.txt,word$(a$,i);" ";word$(a$,j);" ";word$(a$,k);" ";word$(a$,m)
C'est l'affichage des caractères de la chaine a$ aux indices: i; j; k; m
Pour faire sur 5 lettres il faut ajouter une boucle (pas n qui sert déjà, disons "p").
et l'affichage de a$ à l'indice p.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
    for i=1 to n 
       for j=i+1 to n
          for k=j+1 to n
             for m=k+1 to n-1 ' si tu veux 
                #w.txt,word$(a$,i);" ";word$(a$,j);" ";word$(a$,k);" ";word$(a$,m)
             next m
          next k
       next j
    next i

[BBouille]

Il manque for l=k+1 to n et donc for m=l+1 to n non?
Mais c'est monstrueux comme boucles il me semble.
Je ne parviens déjà pas à remplir un fichier text pour i = 1.

[valentin03]

Il manque en effet le "l" entre le "K" et le "m"
mais ça n'a pas grand importance car on donne les noms qu'on veut aux variables, tant que l'algo reste cohérent.
Tu peux donc ajouter une boucle "l=1 to k + 1", Et la "m" devient: "m=1 to l + 1".

[BBouille]

Oui merci mais je ne vois toujours pas comment je pourrai atteindre des temps de calcul décents ni même comment sauvegarder les données par étapes intermédiaires.
Comme je n'ai jamais sauvegardé 9.034.502.400 enregistrements dans une base de données et comme ça n'a pas grande importance je te demanderai d'encoder ce petit programme et de le lancer.

[WhiteCrow]

Bonjour,

voilà un problème de combinatoire plutôt classique. Si tu ne désires que dénombrer l'ensemble des 5-combinaisons constructibles à partir du multi ensemble composé des lettres (on omet donc les deux jockers) du scrabble francophone c'est «relativement» simple. Le nombre total de 5-combinaisons est 117600.
Une méthode pour y arriver : les fonctions génératrices.

L'idée de base est simple, ce que tu cherches à calculer est le nombre r de partitions distinctes de l'entier 5 en 26 entiers (Na, Nb, Nc, … , Nz), i.e. r=Na+Nb+…+Nz, avec la contrainte supplémentaire que 0≤Na≤9 (le nombre de jeton A) et 0≤Nb≤2 (le nombre de jeton B) et … 0≤Nz≤1 (le nombre de jeton Z). Ensuite il faut remarquer que r est l'exposant de x⁵ de l'expansion du polynôme P=(1+x+x²+...+x⁹) × (1+x+x²) × … × (1+x).
Un logiciel de calcul symbolique donne pour P :


Les coefs de ce polynôme te donnent tous les dénombrements de tirage possible.
Si tu ajoutes les jokers, tu obtiens 141878 tirages distincts de 5 jetons, et 2954029 tirages distincts de 7 jetons.