J'ai une petite question:
Imaginons un nombre L, appellé Lignes et un nombre C, appelé Colonnes.
Je prend C éléments que je prends L fois.
J'aimerai une formule pour calculer le nombre de permutations des ces objets.
Exemple:
L=2 et C=2
Je prends 2 éléments 2 fois:
[1][1][2][2]
Les permutations sont:
1) [1][1][2][2]
2) [1][2][1][2]
3) [1][2][2][1]
4) [2][2][1][1]
5) [2][1][2][1]
6) [2][1][1][2]
Merci de m'aider...
Bonjour.
Cherche dans les "k parmi n"
Ici, je dirai 2 parmi 4 qui vaut :
4!/[(4-2)!2!]=6
Bonjour,
Voilà l'approche que j’ai eu l'idée d’utiliser ; ça vaut ce que ça vaut, mais je pense que c'est un bon début...
Le problème est de partir d'un ensemble X avec N = LC éléments, et d'affecter à chaque élément un nombre de 1 à L, de sorte qu'il n'y ait jamais plus de C éléments affectés du même nombre. (On pourrait dire "couleur" au lieu de "nombre" pour être plus "parlant").
Il y a Comb(N,C) = N! / ((N-C)!C!) manières de choisir C éléments dans X, auxquels on affectera la "couleur" 1. Il reste alors (N-C) = (L-1)C éléments, à colorier avec (L-1) couleurs. On a donc la récurrence
U(L,C) = Comb(LC,C) x U(L-1,C)
où U(L,C) est le nombre de manières de colorier LC éléments avec L couleurs, avec exactement C éléments de chaque couleur. Comme clairement U(1,C) = 1 pour tout C, on trouve, si je ne m'ai pas trop gouré (les factorielles se simplifient pas mal):
Mais ce n'est pas fini, car on a choisi un ordre particulier pour les couleurs: là encore, si je ne m'ai pas vautré grossièrement, il faut diviser par L!, d'où pour le nombre de solutions à ton problème:
nombre de solutions = U(L,C) / L! =
Tout ça est à vérifier et à revérifier de très près...
-- françois
ton exemple n'est vraiment pas clair du tout Herbiti (mais vraiment alors pas du tout) neanmoins je crois avoir une idée de ce que tu cherches.
Je vais prendre une exemple beaucoup plus clair : plusieurs interrupteurs electriques branchés en parrallèle. Un interrupteur peut avoir 2 état : ouvert ou fermé.
Dans ce cas le nombre de combinaison possible est 2^n
(n designant le nombre d'interrupteurs et 2 car chaque interrupteur peut prendre 2 etat)
Le nombre de combinaison possible est :
le nombre d'etat que peut prendre la variable ^le nombre de variable
Voila j'espere avoir repondu a ta question
Rebonjour,
Au vu des autres posts, je m'ai effectivement vautré -- mais pas grossièrement, enfin pas tant que ça...
C'est vrai que prendre L = C = 2 comme exemple, ce n'est pas très clair... Mais ma formule donne 4! / (2!^2 x 2!) = 3 dans ce cas, donc il y a plantage...
Je crois que c'est la division par L! à la fon qui est foireuse.
Mais après tout, il faut bien en laisser un peu aux autres
-- françois
Anthonaille, ce que tu dis est tout à fait juste mais je ne pense pas que cela puisse s'appliquer à un exemple du type de celui d'Herbiti.
Je peux me tromper mais on a ici :
C "objets" qu'on veut arranger parmi C*L éléments.
Une formule serait donc C parmi CL, ce qui vaut :
(CL)!/[(CL-C)!C!]
Bon un autre exemple:Envoyé par Anthonaille
L=3 et C=3
Je prends 3 éléments 3 fois:
[1][1][1][2][2][2][3][3][3]
Je veux le nombre de toutes les permutations de cet ensemble.
L=3 et C=2
Je prends 2 éléments 3 fois:
[1][1][1][2][2][2]
L=2 et C=3
Je prends 3 éléments 2 fois:
[1][1][2][2][3][3]
Et j'aimerai une formule pour un C et un L quelconque
Merci de m'aider...
Merci de lire les réponses
désolé :S...Merci de lire les réponses
j'ai calculé avec L=3 et C=2 que ça valait 16 et la formule me donne 15, ais-je compté une permutation en trop ou ta formule est fausse?
Je pense que mon résultat est OK si on vire la divison finale par factorielle (L). Autrement dit, il n'est pas OK si on ne le corrige pas
Pour L=2 et C=3, on a les 15 arrangements suivants:
33xxxx x33xxx xx33xx xxx33x xxxx33
3x3xxx x3x3xx xx3x3x xxx3x3
3xx3xx x3xx3x xx3xx3
3xxx3x x3xxx3
3xxxx3
où chaque suite [xxxx] est l'une des 6 obtenues pour L=2 et C=2. D'où 90 solutions, ce qui colle bien à mon résultat "rectifié".
Le schéma de dénombrement illustré ci-dessus donne probablement une manière plus simple de raisonner que mon calcul usine à gaz (et un peu bourrin?)
-- françois
merci beaucoup
Décidément je suis une quiche en proba, statistiques, dénombrement etc...
Si quelqu'un pouvait m'expliquer pourquoi mon raisonnement est faux, j'en serais très heureux.
Ton raisonnement est OK! Il s'agit bien de prendre C objets parmi L*C. Mais on ne peut pas s'arrêter là, il t'en reste alors L*C-C = (L-1)*C, parmi lesquels il faut encore en prendre C, et ainsi de suite...Décidément je suis une quiche en proba, statistiques, dénombrement etc...
Si quelqu'un pouvait m'expliquer pourquoi mon raisonnement est faux, j'en serais très heureux.
Cela dit, je suis pas mal une quiche aussi, j'ai un peu tendance à tout diviser par une factorielle bien choisie dès que les nombres deviennent un peu grands...
-- françois
Merci !
Tant que ça simplifie faut pas se gênerCela dit, je suis pas mal une quiche aussi, j'ai un peu tendance à tout diviser par une factorielle bien choisie dès que les nombres deviennent un peu grands...
J'aimerai un algo récurssif pour afficher toutes les permutations ci-dessus.
Est-ce possible que vous me donniez l'algo ou je vais voir dans le forum informatique...
Merci
Je dois avoir ça dans mes archives, probablement pas pour ce problème-là précisément, mais facilement adaptable...
Je dirais qu'étant donnée une "permutation" pour (L,C) donnés, soit un tableau de L*C entiers compris entre 1 et L, le jeu est d'insérer la "couleur" (L+1) partout où c'est possible, ce qui peut se faire par une simple boucle (pas besoin de rendre récursive la boucle interne, c'est ce qu'on appelle une "tail-recursion").
On peut (on doit!) créer un tableau de L*C+C éléments, et pour i=0 à LC+1, insérer soit l'élément du tableau original, soit la "couleur" L+1; quand on a inséré C fois la valeur (L+1), le reste s'en déduit. On peut déduire ça de la représentation binaire de i...
Ahem... à mettre en forme! Je te tiens au courant.
-- françois
P.S. - Si j'ai ça dans mes tuyaux, ça sera sûrement en C. Ca te va, ou tu préfères du pseudocode style Pascal?
du C, c parfait
J'aimerai cet algo en c++, puisque je programme en c++ mais si tu l'as en c, c super
Bonjour,
Voilà un algorithme récursif pour ton problème d'énumération. C'est du C++ (je n'utilise pratiquement plus C tout court), mais il est tellement simple qu'on ne voit pas la différence (à part les commentaires en //...).
Pour l'affichage j'ai préféré utiliser le bon vieux printf() plutôt que les iostreams, mais c'est sans importance.
Quelques explications: la fonction colorier(N,P,C,K,m) fait tout le boulot!
C[j] indique combien de fois la couleur j est encore disponible ;
K[i] est la couleur de l'objet i ;
N est le nombre d'objets, P le nombre de couleurs (attention, par rapport à tes notations! c'est bien N, et non N*P, le nombre d'objets).
m est le premier objet à colorier (pour ne pas saloper ce qui a déjà été fait!) Quand m = N, la récurrence se termine.
Initialement C[j] = N/P si toutes les couleurs doivent être utilisées le même nombre de fois (comme dans ton problème), mais ce n'est pas obligé.
L'idée est d'attribuer à l'objet K[m] toutes les couleurs encore utilisables, et ensuite de récurser sur les objets restants (à partir du (m+1)-ème).
Si tu as besoin de plus d'explications, n'hésite pas -- j'ai pondu ça au débotté hier soir, d'où l'absence de commentaires...
-- françois
Le code:
void imprimer (int N, int *K)
{
for (int j = 0 ; j < N ; j++) printf ("[%d]", K[j]) ;
getchar () ; // printf ("\n") ;
}
void colorier (int N, int P, int *C, int *K, int m)
{
if (m < N) {
for (int j = 0 ; j < P ; j++)
if (C[j] > 0) {
K[m] = j ; C[j]-- ;
colorier (N, P, C, K, m + 1) ;
C[j]++ ;
}
}
else imprimer (N, K) ;
}
int main (int argc, char *argv[], char *envp[])
{
const int N = 6 ;
const int P = 3 ;
int K[N] ;
int C[P] ;
for (int j = 0 ; j < P ; j++) C[j] = N / P ;
colorier (N, P, C, K, 0) ;
return EXIT_SUCCESS ;
}
Pfff... les indentations sont complètement bousillées! Heureusement que ce n'est pas trop alambiqué...
c génial
Merci beaucoup
Bonjour,
Voilà ce que j'ai trouvé par hasard, en cherchant tout à fait autre chose. Attention les yeux, la référence fait pro: Bourbaki, Algèbre, Chapitre 1: Structures algébriques, §5, n°1, rectification à la page 58 (p.165):
Ouf. C'est bien ton problème, avec n = LC, m = L, et p_1 = ... = p_m = C.Lorsque la multiplication est commutative, pour m et n entiers > 0, et pour toute famille, on a:
la somme étant étendue à toutes les suites
étant le nombre d'applications de [1,n] sur [1,m] prenant
Donc ma formule était correcte!Ça fait plaisir de se voir confirmer par le Maître!
-- françois
P.S. - C'est la dernière fois que je recopie du Bourbaki en TeX.
