Tirer une combinaison par son indice

PetitLutinMalicieux

Bonjour

nicolas.patrois a dit :

PetitLutinMalicieux a dit :

• Ni ordre, ni répétition -> c'est une combinaison. $C_n^k=\frac{n!}{k!(n-k)!}$. Archétype: quantité de grilles de loto. $C_{49}^6\approx 13.9M$
• Ordre, sans répétition -> c'est un arrangement. $A_n^k=\frac{n!}{(n-k)!}$. Archétype : quantité de podiums différents parmi une foule de candidats. $A_n^3$
  
• Ordre et répétition -> c'est une p-liste. $k^n$. Archétype : quantité de fichiers de n bits : $2^n$
• Sans ordre mais répétition -> combinaison avec répétition. $\Gamma_n^k=C_{n+k-1}^k$. Archétype : quantité de dominos $\Gamma_7^2=C_8^2=28$
  

Dans le module itertools de Python, c’est, dans le même ordre :

• itertools.combinations
• itertools.permutations (en utilisant le deuxième paramètre)
• itertools.product
• itertools.combinations_with_replacement
  

Merci d'avoir indiquer itertools. C'est mignon. Et productif. Mais il y a un gros défaut : si je demande la 2573432ème grille de loto, python va t'obliger à créer les presque 14 millions de grilles de loto. Pas cool. Et parfois, même pas faisable. Alors qu'il y a un algorithme simple pour trouver cette satanée grille. Il suffit de trouver l'ordre croissant des numéros. Si le numéro 1 n'est pas coché, on peut enlever toutes ces grilles de la quantité totale. Elles sont en quantité $C_{48}^5$. Si le numéro 2 n'est pas coché, on recommence. Soit $C_{47}^5$ enlevés supplémentaires. etc.

Au final :

#!/usr/bin/python3

# (...)
N=int(sys.argv[1])
K=int(sys.argv[2])
ind=int(sys.argv[3])
res=[]

v=1
r=ind
while (len(res) nCp(N-v,K-1-len(res))) :
        r -= nCp(N-v,K-1-len(res))
        v=v+1
    res=res+[v,]
    v=v+1
print(res)

Et on obtient :

<code>$ ./tiragecombinaisonparindice.py 49 6 2573432
[2, 9, 24, 25, 33, 40]
$ ./tiragecombinaisonparindice.py 49 6 1
[1, 2, 3, 4, 5, 6]
$ ./tiragecombinaisonparindice.py 49 6 13983816
[44, 45, 46, 47, 48, 49]
$ ./tiragecombinaisonparindice.py 5 3 8
[2, 3, 5]
$ ./tiragecombinaisonparindice.py 5 3 9
[2, 4, 5]
$ ./tiragecombinaisonparindice.py 5 3 10
[3, 4, 5]

La 2576432ème grille de loto est donc celle qui coche 2, 9, 24, 25, 33, 40.

Les trois derniers permettent d'obtenir une répartition spécifique, quand on a fixé la quantité d'objets tirés, avant de savoir si chacun est choisi, ou non.

Ici, on sait qu'on va tirer au hasard 3 parmi 5. Il y a donc 10 possibilités. On peut tirer un nombre entre 1 et 10. Et après le programme donne les éléments tirés.<br>

PetitLutinMalicieux

Merci au modérateur qui a corrigé l'affichage.

[À ton service. AD]