Discussion :

[sloshy]

Bonjour,

Je dispose d'un alphabet composé de X caractères et d'un tableau comprenant pour chaque caractère son nombre d’occurrence. Je souhaite calculer le nombre d'entrée distincte qu'il est possible de réaliser. Je souhaite aussi mettre en place un algo me permettant d'afficher ces possibilité.

Exemple:

Alphabet: "a, b, c"
Occurence: 4 x A, 2 x B et 3 x C.
Sortie:
Il y a X possibilités:
AAAABBCCC
BAAAABCCC
BBAAAACCC
...

Malheureusement, j'ai beaucoup de mal à conceptualisé tout ça, et je viens donc vous demander un coup de main.

[Zavonen]

Dans l'exemple que tu donnes le nombre des possibilités pour le placement des A est C4,9 (nombre de combinaisons de 4 éléments dans un ensemble à 9.
Pour chaque position possible des A Il y a C2,5 positions possibles pour les B, les A et les B étant placés il n'y a plus qu'une seule possibilité pour les C.
Le nombre cherché est donc le produit C4,9 par C2,5 soit sauf erreur 1260.
Bon maintenant compter c'est une chose lister s'en est une autre.
Mais en fait il suffit d'un algo qui liste toutes les parties à p éléments d'un ensemble à n éléments.
Voir par exemple cette page avec des exemples en python:
http://gilles.dubois10.free.fr/Bases/Ensembles/cpn.html

[sloshy]

Bonjour,
Si j'ai bien compris:
- Je calcul d'abord l'ensemble N (qui est la somme du nombre d’occurrence de chaque lettre de mon alphabet).
- Pour chaque lettre de l'alphabet (sauf la dernière ?), je calcul C(M, N) ou M est le nombre d’occurrence de ma lettre et N mon ensemble.

Par contre, j'ai pas compris comment tu as réalisé ton produit.
j'ai pas non plus compris pourquoi la dernière lettre n'était pas à calculer.

(désolé, mes notions de math sont assez mauvaise :/)

Merci pour ta réponse, néanmoins, je pense qu'il me manque des notions de math pour pouvoir la comprendre. je vais donc commencer par essayer de comprendre bien ta réponse, pour ensuite généraliser le calcul pour un alphabet donné.

pour l'implémentation, je verrai ça dans un second temps

[pseudocode]

Bonjour,
Si j'ai bien compris:
- Je calcul d'abord l'ensemble N (qui est la somme du nombre d’occurrence de chaque lettre de mon alphabet).
- Pour chaque lettre de l'alphabet (sauf la dernière ?), je calcul C(M, N) ou M est le nombre d’occurrence de ma lettre et N mon ensemble.

Tu as 9 cases vides:
|__|__|__|__|__|__|__|__|__|


Tu places 4 "A" dans les 9 cases vides:
|__| A |__| A | A |__|__| A |__|

(il y a C4,9 configurations possibles)


Il te reste 5 cases vides:
|__|...|__|.......|__|__|...|__| |__|__|__|__|__|


Tu places 2 "B" dans les 5 cases vides:

|__| B |__| B |__|

(il y a C2,5 configurations possibles pour chacune des C4,9 configurations précédentes -> C2,5 * C4.9 configurations au total)


Il te reste 3 cases vides:
|__|...|__|...|__| |__|__|__|


Tu places 3 "C" dans les 3 cases vides:
| C | C | C |

(il y a une seule configuration pour chaque configurations précédentes --> 1 * C2,5 * C4.9 configurations au total)

[sloshy]

Bonjour,
Merci pour l'explication (j'avais continué à lire de la documentation sur le net).

Dans le cas qui m'occupe, j'ai cru comprendre qu'il s'agissait d'une permutation avec répétition. J'ai compris ce qui y était expliqué et comment calculer le nombre de permutation possible. (dans mon cas, avec 250 classes et 1Ko de donnée bien dispersé, le nombre de permutation devient gigantesque).

Le but initiale était de crée un algo de compression basé sur le bruteforce.
En gros, je divisais mon fichier en paquet de quelques Ko. Ensuite pour chaque paquet, je crée une méta donnée comportant le nombre d’occurrence de chaque caractère et un checksum (environs 550 octets en tout). ensuite je stockais les métadonnée dans le fichier. Le taux de compression était important (suivant la taille choisie du paquet), quand j'ai eu fini le compresseur, j'ai voulu m'attaquer à la partie décompression. je lisais donc le nombre d’occurrence de chaque caractère et vous venez de me permettre de calculer le nombre de permutation maximal possible afin d'obtenir le paquet initiale.

ça représente bien trop de calcul, ça doit prendre quelques millier de millénaire (ce qui est dommage car j'arrivais à faire tenir le contenu d'un DVD sur une disquette ^^')