Discussion :

[Jlmat]

Bonjour,

Je ne sais pas si mon sujet peut s'inscrire ici, car c'est surtout une vérification par des matheux d'une formule de dénombrement dont j'ai besoin dans la rédaction d'un tuto pour vérification d'échantillons de tests. J'ai cherché un forum Maths ou statistiques, mais je n'ai pas trouvé, alors je post ici car mes souvenirs sont un peu lointain dans ce domaine.

Voici le sujet :

Je dois effectuer des tests sur un grand nombre de possibilités. Je n'ai pas déterminé les limites de mes paramètres et c'est pour cette raison que j'ai besoin d'une justification théorique. Je n'en suis donc pas encore à élaborer un algorithme.

Problème : Je voudrais savoir combien il y a de possibilités d'avoir des échantillons de 100 entreprises déterminées qui se répartissent dans un échantillon de 1000 villes prises dans un ensemble de toutes les villes de France, soit 39192 villes, villages etc avec un code postal...
Les couples résultats ont le format suivant : (entreprises, ville) dans cet ordre et il ne doit pas y avoir deux couples semblables dans l'ensemble des couples viables.

Pour des raisons de limites logicielles et matérielles, nous prenons un échantillon test de 1000 villes par exemple (sans répétition de villes dans l'échantillon). Mais je voudrais connaitre au final, le nombre de tests possibles sur l'ensemble des villes de France par le biais des tests sur les échantillons.

Variables du problème:

- Ei = {1..100} entreprises distinctes (E).
- Vi = {1...39192} villes (V).
- On sélectionne un échantillon de k villes distinctes parmi ces 39192 (pas de doublon de ville dans chaque échantillon).
- On cherche le nombre de façons distinctes d'affecter ces 100 entreprises (toutes utilisées, chacune dans une ville différente) à 1000 villes prises dans un échantillon choisi.
- Dans chaque couple, l’entreprise est en première position et la ville en seconde, et chaque couple doit être unique.

On veut compter le nombre de possibilités maximales pour tous les échantillons possibles de villes (sans répétition de villes ni doublon de couple).

Ntotal : nombre total de villes (ici 39192)
k : taille de l’échantillon de villes (exemple : 1000, etc.)
p : nombre d’entreprises à positionner (=100, déterminées)

Formules :

- Choisir un échantillon de k villes parmi 39192 => pas de répétition, ni ordre, que paris soit en 10ème ou en 100ème position dans l'échantillon n'a pas d'importance du moment que l'on a pas deux fois Paris...
donc pour moi, c'est une combinaison : C(Ntotal,k). ëtes-vous d'accord?
- Ensuite, il me faut Associer les n entreprises déterminées aux villes de l'échantillon, sans doublons, mais ici l'ordre est important car le couple (Textronic, Paris) est différent de (Paris, Textronic) qui doit être écarté.
donc, c’est un arrangement sans répétition : A(p,k). êtes-vous d'accord?
- et donc, j'arrive à ma formule finale qui prend en compte tous les couples possibles pour les tests sur tous les échantillons :

Nombre total=C(Ntotal,k)×A(k,p).

Merci de me dire s'il y a une faille dans mon raisonnement!
A+

[tbc92]

La question n'est pas totalement claire.
Tu parles de villes et d'entreprises, et dans mon monde à moi, je comprends qu'on a un recensement des entreprises existantes (l'usine de chaussures xxx existe, dans la ville de Lyon). A priori, je fais fausse route.
On aurait donc en fait 100 entreprises 'nouvelles', nommées E001, E002,... E100.
Et on a 39192 communes C00001 , C00002, ... C39192
Les entreprises n'existent pas encore, et on va implanter ces 100 entreprises dans 100 villes. Et on s'intéresse au nombre de façons de choisir les villes pour chacune des 100 entreprises.

Clarification n°1 : Est-ce qu'il peut y avoir plusieurs entreprises dans la même ville ? Dans la suite, je pars du principe que OUI, il peut y avoir plusieurs entreprises dans la même ville.

Pour des raisons diverses, tu commences par choisir un échantillon de 1000 villes. Mais cette étape ne fait que perturber le raisonnement. Et même en terme de programmation, je doute que ça apporte quoi que ce soit.

Pour l'entreprise E001, on a 39192 choix possibles.
Pour l'entreprise E002, on a 39192 choix possibles.
Etc
Au final, on a 39192^100 choix possibles.

[Jlmat]

Merci tbc92 d'avoir pris le temps d'examiner le problème.

La question n'est pas totalement claire.
Tu parles de villes et d'entreprises, et dans mon monde à moi, je comprends qu'on a un recensement des entreprises existantes (l'usine de chaussures xxx existe, dans la ville de Lyon). A priori, je fais fausse route.
On aurait donc en fait 100 entreprises 'nouvelles', nommées E001, E002,... E100.
...
Clarification n°1 : Est-ce qu'il peut y avoir plusieurs entreprises dans la même ville ? Dans la suite, je pars du principe que OUI, il peut y avoir plusieurs entreprises dans la même ville.

Pour des raisons diverses, tu commences par choisir un échantillon de 1000 villes. Mais cette étape ne fait que perturber le raisonnement. Et même en terme de programmation, je doute que ça apporte quoi que ce soit.
...

J'ai pris cet exemple de couple (entreprise, ville) de manière totalement fictive et ne correspond pas à une réalité d'un processus réel... J'aurais pu prendre (livre, étagère) ou (étudiants, université)...
Oui, je n'ai peut être pas été assez clair!

Le but de mon test est de quantifier un nombre de possibilités qui puissent être représentées dans le pire des cas aux possibilités graphiques maximales d'un écran, donc par un pixel. Ainsi, un écran de 1000 X 800 = surface de dessin maximal = 800 000 pixels, donc 800 000 couples solutions. Cela dans le but de rechercher des valeurs limites et de sécurité, y compris en terme de temps d'exécution de rafraichissement d'écran de gestion mémoire... La représentation graphique d'une entité (couple solution : entreprise/ville) peut se représenter par un pixel de couleur ou une petite grille. Un clic sur la grille ou un pixel et on extrait l'information.

Clarification n°1 : non, une ville = une entreprise (une enseigne). Mais une même enseigne (par exemple "Auchan") pourra se trouver dans d'autres villes. Mon exemple ne semble peut être pas réaliste, mais ça n'est pas le but, c'est uniquement pour un test d'extraction d'une information sur une grille qui représente un ensemble de possibilités.

Je crois que pour tester la solution que je propose, on pourrait ramener les variables à de toutes petites valeurs et lister les solutions. Par exemple:
- Ei = {1..2} échantillon de 2 entreprises distinctes: E1 et E2.
- Vi = {1..6} 6 villes = ensemble des villes : V1..V6
- k = taille de l'échantillon de villes = par exemple k = 3 villes parmi les 6
=> étape 1 : choisir un échantillon de 3 villes parmi 6 => avec la formule donnée, je trouve 20 échantillons possibles.
=> Et ensuite pour l'étape 2, je répartis mes 2 entreprises dans 2 des 3 villes sélectionnées de mon échantillon (car je n'ai que 2 entreprises), ça me donne avec ma formule, 6 façons (couples) de prendre 2 entreprises dans un échantillon de 3 villes.
et donc au final, avec tous les échantillons ma formule finale me donne :

Nombre total = C(6,3) × A(3,2)= 20 × 6 = 120. Je vais lister les 120 couples (entreprises/villes) pour vérifier s'il n'y a pas de doublons...

[tbc92]

On va commencer par une question plus simple.
Il y a 1000 Villes en France. Du coup, je supprime l'étape 1 (choisir 1000 villes parmi les 39192). Si on arrive à se comprendre avec cette simplification, on pourra ensuite voir l'impact de cette première étape.
L'entreprise E001 peut être dans l'une ou l'autre des 1000 villes.
L'entreprise E002 peut être dans l'une ou l'autre des 999 villes restantes.
L'entreprise E003 peut être dans l'une ou l'autre des 998 villes restantes.
etc.
Au total, on a 1000*999*998*997* ...*902*901 possibilités.

Dans ton comptage ( les 120 solutions), tu as des doublons.
Tu peux par exemple choisir dans l'étape 1 les villes (V001, V002, V003) , ou encore les villes (V001, V002, V004).
Et dans ces 2 choix, tu peux au final avoir la combinaison (E001-V001, E002-V002) ; cette solution est donc comptée 2 fois (et même plus)

[Jlmat]

On va commencer par une question plus simple.
Il y a 1000 Villes en France. Du coup, je supprime l'étape 1 (choisir 1000 villes parmi les 39192). Si on arrive à se comprendre avec cette simplification, on pourra ensuite voir l'impact de cette première étape.

Exact, tu m'a convaincu, il faut supprimer l'étape 1.
Je réfléchis à la suite ...
Bonne soirée!

[Flodelarab]

Bonjour

• Il y a un sous-forum mathématiques.
• Ne parle pas d'arrangement. C'est faux. Il n'existe pas d'entreprise "Paris" et pas de ville "Textronic".
• De ce que je comprends, on calcule ceci :
  
  • On tire 1000 villes parmi 39192, indépendamment de l'ordre et sans répétition. C'est donc une combinaison. Jusqu'ici, on est d'accord.
  • On tire 1000 entreprises parmi 100, dans l'ordre (car affecter Textronic à Paris et Suptronic à Lyon n'est pas la même chose qu'affecter Suptronic à Paris et Textronic à Lyon), et avec répétition (nécessairement puisque 1000>100). C'est donc une p-liste.
  
  En gros, ton premier tirage est un sous-ensemble, et le second est un anagramme.

Conclusion, la quantité de situations possibles est :


[edit] Arf. Latex est à nouveau en rade. Voici :
C_{39192}^{1000} \times 100^{1000}
[/edit]

Bon courage !

[Jlmat]

Bonjour,

Pourquoi faire compliqué quand on peut faire simple?
C'est vrai que si je prends deux ensembles finis :
- E = {E1...Ex} un ensemble d'"entreprises"
- V = {V1...Vy} un ensemble de "villes"

Et que l'on souhaite constituer tous les couples (Ei,Vj) avec les contraintes suivantes :
- Les couples sont uniques (pas de doublons)
- Une entreprise peut apparaître sur plusieurs villes, mais une ville ne peut recevoir qu'une seule entreprise
- L'ordre est strict : (Entreprise, Ville)
La solution est un produit cartésien: N=E ×V. Exemple E = 2, V = 3 => N = 6 : {(e1,v1),(e1,v2),(e1,v3),(e2,v1),(e2,v2),(e2,v3)}

Étape 1: Objectif Mon véritable objectif est de trouver les bonnes valeurs limites et interdépendantes du nombre d'entreprises Ep et de villes Vn (ça pourrait être n'importe quel autre paramètres) pour obtenir un nombre de possibilités représentées sur un écran d'ordinateur. Par exemple un Écran de 1000 × 800 pixels => 800 000 pixels.
Donc, je suis obligé d'introduire un échantillon d'entreprises ou de villes pour approcher et voir qu'elles seraient les contraintes!

Soit un échantillon de k Villes, le nombre d'échantillons possibles serait N = E × k, mais au final ce que je veux, c'est combien de couples maximum uniques (entreprises, villes) est possible à partir de E Entreprises associées à k villes prises dans V Villes?

Étape 2 : Solution nombre de couples Possibles

D'après moi :

- Il y a répétitivité une entreprise peut être associée à plusieurs villes.
- il y a importance de l'ordre => couples ordonnés (Entreprise, Ville).

J'avais pensé à un arrangement, mais il semble que non, parce qu'un arrangement se fait sur un même ensemble d'après ce que j'ai compris, or on a deux ensembles, il s'agit donc bien d'un produit cartésien.

Le nombre de solution semble bien : N = E × k si k = échantillon de villes ou encore N = k × V si k = échantillon d'Entreprises

Bon si c'est ça, ça me simplifie le reste.

Étape 3 : Valeurs limites

Notre Limite est la Taille de la surface graphique d'un écran SCR : On prends 800 000 pixels
La contrainte est donc : N ≤ 800 000 couples, soit E × k ≤ 800 000

donc, je peux intervenir en fixant une variable à une valeur et calculer l'autre variable.

Si je prend E = 100 entreprises => E × 100 ≤ 800000 => E ≤ 8000

La formule finale est donc E × k villes ≤ SCR ou k Entreprises × V ≤ SCR

Bon, si vous êtes d'accord avec mon raisonnement, je mets résolu. merci pour votre aide.

[tbc92]

Dans un écran, si on a 800000 pixels qui sont tous soit noir, soit blanc, ça fait beaucoup plus que 800000 images possibles.
Le premier pixel peut être blanc ou noir : 2 possibilités
Le deuxième pixel peut être blanc ou noir : 2 possibilités, donc 2x2=4 possibilités avec 2 pixels
Le troisième pixel peut être blanc ou noir : 2 possibilités, donc 2x4=8 possibilités avec 3 pixels
Etc.

Guesset a utilisé un mot nouveau, c'est le mot AGENCE.
Tu as Plein de villes, tu as des entreprises, et chaque entreprise a 1 ou plusieurs agences.
Au total, tu as 100 Agences, avec au maximum 1 agence par ville.
En prenant des scénarios extrêmes, peut être que ces 100 agences sont toutes de la même entreprise, ou à l'autre extrême, ces 100 agences sont toutes issues d'entreprises différentes.

Si l'entreprise E001 a des agences dans 3 Villes V00005, V00010 et V00015, et l'entreprise E002 a 1 agence dans la ville V34567, cette solution sera codée (E001V00005, E001V00010, E001V00015, E002V34567), l'ordre n'ayant pas d'importance, on classe ces 'mots' par ordre alphabétique, pour avoir une écriture normalisée, et éviter les doublons.

[Jlmat]

@ tbc92 :

Je cherche à simplifier, mais tu compliques à nouveau. Non pas que la solution que tu proposes est inintéressante, mais je vais la réfuter pour les deux raisons, exposées plus loin:

Dans un écran, si on a 800000 pixels qui sont tous soit noir, soit blanc, ça fait beaucoup plus que 800000 images possibles.
Le premier pixel peut être blanc ou noir : 2 possibilités
Le deuxième pixel peut être blanc ou noir : 2 possibilités, donc 2x2=4 possibilités avec 2 pixels
Le troisième pixel peut être blanc ou noir : 2 possibilités, donc 2x4=8 possibilités avec 3 pixels
Etc.

Guesset a utilisé un mot nouveau, c'est le mot AGENCE.
Tu as Plein de villes, tu as des entreprises, et chaque entreprise a 1 ou plusieurs agences.
Au total, tu as 100 Agences, avec au maximum 1 agence par ville.
En prenant des scénarios extrêmes, peut être que ces 100 agences sont toutes de la même entreprise, ou à l'autre extrême, ces 100 agences sont toutes issues d'entreprises différentes.

Si l'entreprise E001 a des agences dans 3 Villes V00005, V00010 et V00015, et l'entreprise E002 a 1 agence dans la ville V34567, cette solution sera codée (E001V00005, E001V00010, E001V00015, E002V34567), l'ordre n'ayant pas d'importance, on classe ces 'mots' par ordre alphabétique, pour avoir une écriture normalisée, et éviter les doublons.

Observations et conclusion:

1. Oui, effectivement, ta méthode est intéressante car elle permet effectivement d'élargir le nombre de possibilités...

2. Mais je ne la retiens pas pour mon besoin car comme je l'ai déjà signalé, le thème de l'entreprise est fictif et ne correspond pas au fond du problème qui est de contrôler certaines variables déterminées par un utilisateur. Or ces variables pour l'objectif que je poursuis doit être visible non pas en nuances de couleurs mais en zone d'espace (grille). J'ai pris le cas extrême d'un pixel pour une cellule minimale et qui correspond à un clic sur l'écran. Mais c'est vrai que j'aurai pu utiliser des couleurs. Cependant j'ai besoin de cellules unitaires dans la grille qui sera plus visuelle au premier coup d'oeil.

3. Le problème de l'Agence soulevé par notre ami Guesset serait valable sur un problème réel de réseau de transport et de facturation par exemple, mais dans ce cas, on peut parler de catégories à n'en plus finir : marque, société, holding, groupe, agence, filiales etc... Dans mon cas, une cellule de la grille = une entreprise, même deux ou trois Auchan ou Leclerc dans la même ville qui sont possibles dans la réalité seront exclus ici....

Conclusion: Je valide la solution du produit cartésien
Merci pour nos échanges.

[Guesset]

Bonjour,

L'exclusion mutuelle des entreprises (1 ville -> 0 ou 1 entreprise) change tout.

Le produit ne fonctionne que si les entreprises sont indifférenciées, donc que {(V1, E1), (V2,E2)} = {(V1, E2), (V2,E1)}.

Salutations

[Jlmat]

Bonjour,

L'exclusion mutuelle des entreprises (1 ville -> 0 ou 1 entreprise) change tout.

Le produit ne fonctionne que si les entreprises sont indifférenciées, donc que {(V1, E1), (V2,E2)} = {(V1, E2), (V2,E1)}.

Salutations

Dans mon cas : dans le test, j'ai deux échantillons qui sont fournis : Un échantillon d'entreprises et un autre échantillon pour les villes. Je l'ai dit, c'est un exemple. Mais la formule de contrôle ne s'appliquera que si une variable est changée. On fixe une valeur et on calcule l'autre pour savoir si l'on est dans les limites...
Il ne peut y avoir au niveau de la grille de villes vides ou d'entreprises vides si l'on privilégie soit l'échantillon villes, soit l'échantillon entreprises, ça simplifie...