Lister les parties à 3 éléments de {1;2;3;4;5}

enrouement

Bonjour,
est-ce la meilleur façon de lister les parties à 3 éléments de {1;2;3;4;5} ?

PetitLutinMalicieux

Bonjour
La meilleure façon, c'est toujours par rapport à un critère. Si ton but est de visualiser, je dis "oui". Si ton but est de dénombrer, je dis "non".

On tire 3 parmi 5, indépendamment de l'ordre (un ensemble n'est pas ordonné) et sans répétition, c'est donc une combinaison.
$C_5^3=C_5^2=\frac{5*4}{2}=10$. Pas besoin de dessin, ni tableau.

À noter : la somme des quantités de parties de k éléments parmi 5 donne $2^5$. Ben oui, pour chaque élément, on dit s'il est, ou pas, dans la sélection.
Parties à 0 élément: 1
Parties à 1 élément : 5
Parties à 2 éléments : 10
Parties à 3 éléments : 10
Parties à 4 éléments : 5
Parties à 5 éléments : 1
Somme : $32 = 2^5$

kolotoko

Bonjour,

si lister consiste à écrire la liste des parties à trois éléments, c'est une bonne méthode.

Méthode valable ici parce que le nombre d'éléments est petit.

Si ce nombre était très grand, on ne pourrait que dénombrer, ce qui est déjà pas si mal.

Bien cordialement.

kolotoko

Médiat_Suprème

Pour effectivement lister les parties à 3 éléments, il est plus simple de lister les parties à 2 éléments et passer au complémentaire.

nicolas.patrois

En Python :

>>> from itertools import combinations
>>> for c in combinations("12345",3):
...   print("".join(c))
... 
123
124
125
134
135
145
234
235
245
345

Il a le bon goût de les présenter triées, en plus.

JLapin

@enrouement
Oui, je trouve ta présentation très claire.

GaBuZoMeu

Bonsoir
C'est l'ordre lexicographique, n'est-ce pas ?
On peut lister les parties à $k$ éléments de $\{1,2,\ldots, n\}$ ainsi.

Un truc à faire :
- un algorithme qui donne le n° d'une partie à $k$ éléments dans la liste (sans faire toute la liste jusqu'à trouver cette partie).
- un algorithme qui, étant donné le n°, donne la partie correspondante (idem, sans faire toute la liste jusqu'au n° donné).

gebrane

Voici un programme en Python qui répond à ta première question. est-il conforme ?

from itertools import combinations

n = int(input("Entrez la valeur de n : "))
k = int(input("Entrez la valeur de k : "))
elements = list(range(1, n+1))
partie = [int(input(f"Entrez l'element {i+1} de la partie : ")) for i in range(k)]
comb = sorted(combinations(elements, k))
index = comb.index(tuple(partie)) + 1 if tuple(partie) in comb else None
print("Le numéro de la partie est :", index) if index else print("La partie doit contenir exactement k éléments")

Exemple pourn=5, k=3 et la partie 235, le programme donne 8

GaBuZoMeu

Non.

gebrane

Pourquoi non. Explique.
(Je sais j'ai donné un programme au lieu d'un algorithme et c'est nettement mieux).

GaBuZoMeu

C'est pourtant clair.
Dans la consigne : "sans faire toute la liste jusqu'à trouver cette partie"
Dans ton programme  : "# Générer toutes les combinaisons possibles de k éléments dans la liste d'éléments"

gebrane

Ok J'ai zappé  (sans faire toute la liste jusqu'à trouver cette partie). J'ai tenté ma chance et j'ai fait faux.

Fin de partie

Un algorithme tout pourri pour obtenir cette liste.

On considère un tableau de dimension $5$: $A[0],A[1],A[2],A[3],A[4]$
Le tableau va contenir un nombre écrit en base $2$. $A[0]$ est le chiffre le plus à gauche et $A[4]$ le chiffre le plus à droite.
Il faut une fonction incrémente qui reçoit en entrée le tableau $A$ et qui ajoute $1$ au nombre représenté en base $2$ par $A$

Il y a plus qu'à faire une boucle pour obtenir toutes les valeurs (en base $2$) entre les nombres $0$ et $2^5-1$
Dans chaque passage de la boucle on inclut un test pour compter le nombre de $1$, s'il y en a $3$ on affiche les positions dans le tableau où se trouvent ces $1$.

L'algorithme est tout pourri car si on remplace $5$ par un nombre beaucoup plus grand, le temps d'exécution va devenir rapidement prohibitif mais pour $5$ cela devrait être très rapide sur un ordinateur moderne.

PS.
Si vous êtes intéressé j'ai un algorithme tout pourri qui utilise les nombres premiers pour générer toutes les permutations d'un ensemble à $n$ fixé par avance (le nombre ne peut pas être modifié dans le programme) d'éléments

gebrane

Tu as raison    FDP.  Avec mon programme, pour n=100 et k=10, il tourne sans fin.

Mais ca marche pour n=50 et k=5

Entrez la valeur de n : 50
Entrez la valeur de k : 5
La liste des elements est : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
Entrez l'element 1 de la partie : 5
Entrez l'element 2 de la partie : 10
Entrez l'element 3 de la partie : 20
Entrez l'element 4 de la partie : 35
Entrez l'element 5 de la partie : 45
Le numéro de la partie est : 801441
>

@GaBuZoMeu est-ce que ton programme donne un résultat pour n=100 et k= 10 ?

gebrane

@Fin de partie  a dit
Si vous êtes intéressé j'ai un algorithme tout pourri qui utilise les nombres premiers

Si tu as réussi à écrire un programme en Python avec les nombres premiers ; ça m’intéresse.

Un défi
Est ce que quelqu’un peut donner un programme qui donne un résultat pour n=100 et k=10 avec la liste suivante

Entrez la valeur de n : 100
Entrez la valeur de k : 10

Entrez l'élément 1 de la partie : 5
Entrez l'élément 2 de la partie : 45
Entrez l'élément 3 de la partie : 25
Entrez l'élément 4 de la partie : 35
Entrez l'élément 5 de la partie : 40
Entrez l'élément 6 de la partie : 56
Entrez l'élément 7 de la partie : 59
Entrez l'élément 8 de la partie : 83
Entrez l'élément 9 de la partie : 94
Entrez l'élément 10 de la partie : 98

GaBuZoMeu

Comme ça ?

%time indice([5,25,35,40,45,56,59,83,94,98],100)

CPU times: user 54 µs, sys: 7 µs, total: 61 µs

Wall time: 66 µs

7074315950714

[Edit : corrigé une ligne erronée dans le programme]

GaBuZoMeu

Et ça marche même pour de plus petits exemples.

%time indice([2,3,5],5)

CPU times: user 17 µs, sys: 2 µs, total: 19 µs
Wall time: 23.4 µs

8

gebrane

Tu as réussi!. Bravo.

Qui d'autres peut le faire ?

Fin de partie

@Gebrane

Le programme tout pourri auquel je pensais pour générer les permutations d'un ensemble à $n$ éléments.

Il y a $n$ boucles imbriquées.

($n$ n'est pas une variable mais une valeur fixe dans le programme)

for a1=1,n
{
  for(a2=1,n
 {
  ....
 { 
P2:=A[a1]*A[a2]*.....;
if(P2==P) then print(a1,",",a2.....)

 }
...
}

Préalablement on a initialisé un tableau à $n$ entrées avec $n$ nombres premiers distincts (le plus simple est de prendre les $n$ premiers nombres premiers*) et on a calculé P:=A[1]*A[2]*...

*: on peut prendre $A[1]=1$

NB.
Le programme est tout pourri car quand $n$ augmente les calculs deviennent vite prohibitifs mais pour de petites valeurs cela fait le boulot et c'est facile à coder.

GaBuZoMeu

Le programme que j'ai écrit en python n'a rien de sorcier. Pour savoir le rang d'une liste (strictement croissante), on compte le nombre de listes dont le premier item est strictement plus petit que celui de la liste donnée, puis on récurre en enlevant ce premier item. Le programme fait 7 petites lignes.

PetitLutinMalicieux

#!/usr/bin/python3
import sys
from random import random
 
# Factorielle :
def fact(n):
    res=1
    for i in range(1,n+1):
        res *= i
    return res

# nCp : Combinaison
def nCp(n,p):
    return fact(n)//(fact(p)*fact(n-p))

#print(nCp(49,6))
N=int(sys.argv[1])
K=int(sys.argv[2])

res=[]

v=1
r=int(random()*nCp(N,K)+1)
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(list(map(lambda x:11-x,res)))
print(' '.join(str(x) for x in map(lambda x:11-x,res)))

Ce code est un code dont j'ai eu besoin. Je le livre tel quel. Je ne l'ai pas relu. On voudrait tirer au hasard, mais après, il faut savoir ce qui a été tiré. C'est la question initiale de GaBuZoMeu. La méthode est d'enlever des pans entiers de possibilités en les dénombrant.

PS. Quand je copie-colle du code, j'ai un souci d'affichage une fois sur deux. Je ne comprends pas pourquoi.

GaBuZoMeu

Ton code est illisible. Tu as une entrée "Code" sous le 6e bouton à partir de la gauche. Après on insère son code en mode html </>

Dom

Ha ok. 

On déplace le départ au lieu de commencer à « 1 ». 

GaBuZoMeu

import math

def indice(liste,n) :
    if liste == [] : return 1
    else :
        k = len(liste)
        tete = liste.pop(0)
        queue = [i-tete for i in liste]
        return math.comb(n,k)-math.comb(n+1-tete,k)+indice(queue,n-tete)

gebrane

Tu es diabolique Gabu, avec cette  simplicité.

ton programme donne une valeur juste meme si on entre une liste non croissante

edit

>  indice([5,3,4],5)
indice([5,3,4],5)
8
>  indice([3,4,5],5)
indice([3,4,5],5)
10
>

gebrane

Je crois on peut améliorer ton code pour entrer une liste non croissante, d'abord un code pour faire un tri  stricement croissant et après on applique ton code . je vais y réfléchir

Dom

Je n’y connais rien. Mais 7 lignes… c’est compliqué pour améliorer, non ?

gebrane

Dom tu n'as pas compris

GaBuZoMeu

Bien sûr, je supposais que la liste était rentrée dans l'ordre croissant. Si on veut pouvoir rentrer des listes dans un ordre non nécessairement croissant, il suffit d'ajouter une commande liste.sort() au début, tout simplement

gebrane

Un dernier truc pour finir, normalement l'ordre lexicographique gère les répétions  (la page 112 est bien définie).

On peut chercher  le rang dans ce monde de combinaisons avec répétions.

PetitLutinMalicieux

Merci GaBuZoMeu, mais j'ai fait les choses correctement. La meilleure preuve est que le code est dans un encadré.

gebrane

PetitLutinMalicieux mets ton code dans un fichier texte et attache le

GaBuZoMeu

@PetitLutinMalicieux : es-tu passé par le code HTML en cliquant sur le bouton </> pour insérer ton code python ?

@gebrane : "on peut chercher  le rang dans ce monde de combinaisons avec répétions", d'accord, fais-le.

gebrane

C'est ce que je suis en train de faire.

PetitLutinMalicieux

GaBuZoMeu, 3 remarques :

• Le code html est linéaire. J'ai envie de tout sauf que mon code python soit linéaire.
• Quand on active le mode html </>, il n'y a pas de balises code accessibles.
• C'est le site qui force des choses indues, comme la taille des interlignes, ou le changement du retour chariot en <br>.

La dernière fois, un administrateur est passé. Mais j'admets que ce n'est pas une solution pérenne qu'un administrateur passe toujours derrière.

Ah! Ben d'ailleurs, mon code est rétabli. Merci l'équipe.

Le cadre jaune dans lequel on écrit le code n'est pas une garantie suffisante de bon affichage final.

nicolas.patrois

J’ai trouvé le contournement suivant :

1. Cliquer sur le ¶ puis sur Code.
2. Cliquer sur le </> à droite.
3. Insérer le script entre les balises <code>ici</code>.

GaBuZoMeu

C'est ce que je suggérais à @PetitLutinMalicieux en lui disant de passer par le code HTML (bouton </>) pour insérer son code python.

Tu as une entrée "Code" sous le 6e bouton à partir de la gauche. Après on insère son code en mode html </>

Avec ton mode d'emploi pas à pas, il comprendra peut-être mieux.

gebrane

Voici le programme, avec ton code c'est impossible.

edit

Programme à revoir, voir message de gabu en bas 

gebrane

edit  Programme à revoir <br><br><br>Entrez la valeur de n : 5
Entrez la valeur de k : 3
Entrez l'element 1 de la partie : 1
Entrez l'element 2 de la partie : 1
Entrez l'element 3 de la partie : 2
Le numéro de la partie est : 2
> 

Entrez la valeur de n : 5
Entrez la valeur de k : 3
Entrez l'element 1 de la partie : 2
Entrez l'element 2 de la partie : 2
Entrez l'element 3 de la partie : 3
Le numéro de la partie est : 33

GaBuZoMeu

avec ton code c'est impossible

C'est parfaitement possible en faisant les adaptations ad hoc.

gebrane

J'ai essayé sans succès avec ta façon et j'ai repris mon code qui utilise des fonctions  préprogrammé dans itertools product

( J'ai enlevé les commentaires et ça donne un code de 3 lignes. Les premières lignes c'est pour entrer les données)

Alain24

@enrouement Si tu identifie $1$ avec $0$, $2$ avec $1$, $3$ avec $2$, $4$ avec $3$, $5$ avec $4$ tu obtiens tous les nombres à 3 digitaux (en complétant avec des 0 à gauche) que tu peux écrire en base $4$ : il y en a $4^3$, ainsi tu obtiens un algorithme de complexité

exponentielle.

verdurin

gebrane si on change la question, la réponse change.

Ce n'est guère surprenant.

gebrane

Bonsoir verdurin

Gabu utilise une formule combinatoire très efficace pour calculer cela, surtout pour les grandes valeurs de n. Pour illustrer la difficulté de ce problème, essayez de trouver une formule combinatoire pour les combinaisons avec répétitions et implémentez-la correctement

Acceptes-tu le défi ? 

PetitLutinMalicieux

Pas compris. Les combinaisons avec répétitions ne sont jamais que des combinaisons sans répétitions, à une formule près : $\Gamma^k_n=C^k_{n+k-1}$. Où est le défi ?

Au fait, merci nicolas.patrois. J'essayerai.

gebrane

Bah fait nous comprendre essayez de trouver une formule combinatoire pour les combinaisons avec répétitions et implémentez-la correctement

Ajout je n'ai pas réussi le code,  ça ne donne pas les bons résultats. Si tu réussis bravo

verdurin

Bonne nuit gebrane.

Le problème ne me semble pas bien posé.

Disons que l'on considère les suites croissantes à $k$ éléments pris dans $\{ 1 \dots n\}$ que l'on classe dans l'ordre lexicographique.

L'idée évidente de GBZM s’applique alors sans problème.

Quand à l’implémenter correctement j'en suis effectivement incapable, sauf à y consacrer trop de temps.

Et il me semble que tu l'es aussi.

Je n'accepte pas le défi.

gebrane

verdurin  

Tu préfères perdre par forfait ,  pas de problème

verdurin

En fait il s'agit d'un problème de dénombrement pas spécialement difficile.

Mème si on ne considère pas que des suites croissantes.

gebrane

@verdurin  Tu n'as pas suivi le fil donc tu n'as pas compris le problème.   Gabu a rendu la question délicate avec sa consigne

Gabu demande un algorithme qui donne le n° d'une partie à k éléments dans la liste (sans faire toute la liste jusqu'à trouver cette partie)

Il a dévoilé son programme pour des listes sans répétitions et Je voulais faire de même avec une liste qui contient des répétitions . J'ai échoué lamentablement  le code  ( il me sort des résultats faux) et j'ai repris mon programme qui marche aussi dans cette situation

GaBuZoMeu

@gebrane, est tu sûr que le rang de 2,2,3 parmi les combinaisons avec répétition de trois parmi 1,2,3,4,5 soit 33 ? Moi je trouve 17.

Dans ta liste, avant 2,2,3, tu as par exemple 1,1,2 et 1,2,1 et 2,1,1 : trois fois la même combinaison avec répétition.