Discussion :

[NODIX86]

Bonjour, j'aimerai savoir s'il est possible de générer toutes les 4960 combinaisons sans répétitions de k parmis n avec K=3 et n=32 ? et si oui comment faire?

Merci à vous

si joint un fichier que j'ai trouvé sur le net mais qui se limite à 20 numéro au lieu de 32 et que je n'arrive pas à modidier 20Combinaisons.xls

[vttman]

En excel ça ne me parait pas simple ... mais pour info :

Pour la partie algorithme à transcrire sous excel pour les utilisateurs avertis je pense ,
Faire une recherche sur un article TRES intéressant
=>
Taper "Combinaison sans répétitions Dinoblog"

Là l'auteur de l'article nous livre un programme python avec explications et qui sur un émulateur comme (Trinket )
nous renvoie bien nos 4960 combinaisons

Code :

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

1
2
3
4
5
 
L = ["1","2","3","4","5","6","7","8","9","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W"]
N = 3
G = []
...

=>

'W12'
'W13'
'W14'
'W15'
'W16'
'W17'
'W18'
'W19'
'W1A'
'W1B'
'W1C'
'W1D'
...
'514'
'523'
'524'
'534'
'412'
'413'
'423'
'123'

[unparia]

Bonjour
Je veux bien écrire un tel code.
Mais uniquement s'il a un réel intérêt.
J'attends donc que tu m'exposes clairement la finalité d'un tel listing de la totalité de ces combinaisons possibles.

[Menhir]

En A1, tu mets le nombre d'éléments de ton échantillon (32 dans ton cas).

En A3, B3 et C3, tu mets 1.

En A4, B4 et C4, tu mets respectivement les formules :

Code :

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

1
2
3
=SI(ET(B4=1;B3<>1);MOD(A3;$A$1)+1;A3)
=SI(C4=1;MOD(B3;$A$1)+1;B3)
=MOD(C3;$A$1)+1

Tu copies A4:C4 sur les 4958 cellules du dessous.

[Ben_L]

Bonjour,

Les formules proposées par Menhir fournissent les choix avec répétition et lorsque l'ordre de choix importe (au passage, il y en a 32^3, soit bien plus que les 4960 cas demandés...).

Pour obtenir uniquement les combinaisons, c'est-à-dire les choix sans répétition et lorsque l'ordre importe peu, vous pouvez utiliser les formules suivantes :

• En B2, entrer la valeur de k (le nombre d'éléments à choisir),
• En C2, entrer la valeur de n (le nombre d'éléments parmi lesquels on choisit),
• En B4, utiliser la formule suivante, à valider en matriciel :

  Code :

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

  =SI(OU(ET(A3=0;B3=0;A4=0);A3<>A4);A4+1;SI(SOMME(SI(PRODUITMAT(SI($A$3:A3-$A4:A4=0;0;1);TRANSPOSE(SI($A$1:A$1=$A$1:A$1;1;0)))=0;SI(B$3:B3=B3;1;0);0))=COMBIN(MAX($C$2-B3;1);MAX($B$2-COLONNE()+1;0));B3+1;B3))

Etirer enfin la formule de la cellule B4 à toute la plage souhaitée (ici, B4 : D4964).

Bon, c'est un peu barbare, mais c'est fonctionnel

[vttman]

En A1, tu mets le nombre d'éléments de ton échantillon (32 dans ton cas).

En A3, B3 et C3, tu mets 1.

En A4, B4 et C4, tu mets respectivement les formules :

Code :

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

1
2
3
=SI(ET(B4=1;B3<>1);MOD(A3;$A$1)+1;A3)
=SI(C4=1;MOD(B3;$A$1)+1;B3)
=MOD(C3;$A$1)+1

Tu copies A4:C4 sur les 4958 cellules du dessous.

Pas mal !
Mais j'ai un doute par rapport à ce qu'on entend par "combinaison sans répétition"
je cite
"Une combinaison est donc le choix d'un sous-ensemble de k objets parmi n objets.
...
Ici, nous considérons uniquement le cas des combinaisons sans répétition, ce qui signifie qu'aucun objet ne peut apparaître plus d'une fois"

[unparia]

Bonjour vttman
ton interprétation est erronée et à modifier ainsi :

qu'aucun objet sous-ensemble d'objets ne peut apparaître plus d'une fois

La solution par formules de Menhir, que je salue, est bonne.

[Ben_L]

Bonjour unparia,

Je ne puis que vous donner tort. Les répétitions ne sont pas permises dans une combinaison.
En effet, une combinaison correspond à un tirage simultané sans remise.

Les formules de Menhir correspondent à un tirage ordonné avec remise.

Cordialement

[unparia]

Bonjour Ben_L
Où vois-tu qu'il s'agit de "tirages" ?
Il s'agit de GENERER la liste de toutes les combinaisons (sans doublons de COMBINAISONS) possibles de 3 éléments pris parmi 32 éléments . Ce que fait la solution de Menhir .
Chacune des combinaisons n'y figure qu'une seule fois

PS et ne pas confondre double-pattes et patachon.
Une combinaison est une combinaison (un "cocktail"). Ainsi : la combinaison 10,3,2 et la combinaison 3,10,2 sont le même "cocktail" (la même combinaison). Les permutations d'éléments au sein d'une combinaison ne font pas des combinaisons distinctes !

[Ben_L]

C'est toute l'idée d'une combinaison : tirer k éléments parmi n.

Si tu souhaites te convaincre : vérifie tout d'abord combien vaut C₃₂³.
Il se trouve que l'évaluation de NODIX86 est la bonne : 4960 (soit 32*31*30/(2*3)).
Et si tu n'arrives vraiment pas à me faire confiance, tape donc "32 choose 3" dans wolfram alpha...

D'où vient donc cette formule ?
Pour le numérateur, il s'agit du nombre de choix disponibles pour le 1er tirage (32) multiplié par celui du 2ème tirage (31) et celui du 3ème (30).
Si à chaque tirage, le nombre de choix diminue, c'est bien que les tirages se font sans remise, c'est-à-dire qu'un élément donné ne peut pas apparaître plusieurs dois dans un seul tirage.

Pour le dénominateur, il provient du fait qu'on ne s'occupe pas de l'ordre dans lequel les nombres sont tirés.

La solution fournie par Menhir correspond à des tirages avec remise (un même nombre peut être tiré plusieurs fois) et pour lesquels l'ordre de triage compte.
Ainsi, les formules de Menhir mènent à considérer les tirages 1/2/3 et 3/2/1 comme différents, alors que ce n'est pas justifié si on s'intéresse aux combinaisons.
Un façon simple de se rendre compte qu'il y a un problème, c'est de tirer les formules jusqu'à la ligne 4962. On obtient le tirage suivant : 5/27/32.
Quelqu'un doute-t-il vraiment du fait qu'il ne s'agit pas de la fin de la liste ???

[NODIX86]

Merci de vos réponses mais je ne m'y connais absolument pas en macro, du coup je ne vais pas pouvoir faire grand chose

[unparia]

NODIX86 a répondu à la question que je posais en mon tout premier message (message 3).
Mais il l'a fait ... par message privé
Lorsqu'il l'aura enfin fait ici, il découvrira que ce listing n'est absolument pas nécessaire pour obtenir ce qu'il cherche à déterminer

[vttman]

Bonjour vttman
ton interprétation est erronée et à modifier ainsi :


La solution par formules de Menhir, que je salue, est bonne.

Pas une interprétation, juste une citation de wikiversity.org concernant les combinaisons sans [EDIT]répétitions je voulais diredoublons ...
donc rien à modifier pour moi

4960 = 32! / [(32-3)! * 3!] c'est le nombre de combinaison que voulait NODIX86 ...
Pour la solution de Menhir avec k = n = 3 j'obtiens 29-3+1 = 27 solutions <> 1 car 1 = 3! / [(3-3)! * 3!]
donc qui se mélange les pinceaux ?

[EDIT] Ci joint le tableau avec formules de Menhir et pour expliquer d'où je sors le 29-3+1

[NODIX86]

en fait, c'est pour déterminer les probabilités de toucher la ou les cartes voulues du derniers tirages au jeu du poker chinois (OFC) sur un tirage de 3 cartes parmis un nombre de cartes restantes.
exemple: 4 cartes interessantes à toucher sur un tirages de 3 cartes sur les 16, 18, 20 ou 32 restantes. 32 étant le maximum de cartes inconnues possibles. Du coup le nombre n doit pouvoir être modifiable.

[unparia]

Quel que soit le calcul de probabilités : il ne se fait pas sur la base d'une liste des combinaisons possibles, mais sur des nombres uniquement

[NODIX86]

possible mais je ne connais pas la formule, et ici par exemple pour 5 cartes attendues il suffit de remplacer les 5 1eres lignes par 1 et les autres par 0 et on obtient un nombre de lignes contenant au moins un 1, que l'on divise par le nombre de combinaisons = proba de toucher l'une de ces 5 cartes

[Menhir]

Les formules proposées par Menhir fournissent les choix avec répétition et lorsque l'ordre de choix importe (au passage, il y en a 32^3, soit bien plus que les 4960 cas demandés...).

Mais j'ai un doute par rapport à ce qu'on entend par "combinaison sans répétition"

Dans ce cas, remplacer les formules que j'ai données par :

Code :

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

1
2
3
=SI(B3=$A$1;SI(A3=$A$1;"";A3+1);A3)
=SI(C3=$A$1;SI(B3=$A$1;A4;B3+1);B3)
=SI(C3=$A$1;B4;C3+1)

Ce sont les tirage de k éléments parmi n élément à condition de remettre dans le pool à tirer l'élément qui vient de l'être.
S'il n'y a pas remise en pool, il faut ajouter +1 aux A4 et B4 des formules 2 et 3 et, bien sûr, commencer par 1 2 3 et non pas 1 1 1.

[Ben_L]

Au risque de paraître pénible, ce n'est toujours pas la bonne solution.

Les formules que vous proposez ici, Menhir, fournissent par exemple le tirage 1/3/3.
Elles ne permettent donc pas de supprimer les tirages avec doublons.

D'ailleurs, on peut voir que la 4960ème ligne contient le tirage 15/26/31, ce qui là encore montre que la liste est loin d'être finie...

Une solution fonctionnelle est celle que j'ai donnée plus haut.
Il existe peut-être une version plus simple, obtensible en modifiant l'ordre dans lequel on liste les tirages.
Mais si on veut une solution générale en fonction des nombres n et k, il me semble difficile de simplifier beaucoup plus.

[vttman]

...
Une solution fonctionnelle est celle que j'ai donnée plus haut.
...

Ben_L, sous Excel online comme libreoffice, je n'arrive pas à générer les combinaisons
en appliquant la manip... ?
J'obtiens ceci
=>

[Ben_L]

Cela est probablement dû au fait que la formule proposée est matricielle.
Elle doit être validée en utilisant Ctrl+Shift+Entree.

(j'ai refait le test sur ma version d'EXcel et tout fonctionne semble-t-il très bien)