tamalou
Bonjour,
Est ce que quelqu'un pourrait m'aider svp ?
J'aimerai savoir comment trouver toutes les possibilités de combinaisons pour une suite de nombres svp dans tous les ordres?
ex : 00 00 00 00
00 00 00 01
00 00 00 02
00 00 00 11
00 00 00 22
00 00 00 21
00 00 00 12
J'esperes que vous me comprenez :)
Merci d'avance
Invite
Message de Glozi (sans compte)
Bonjour,
Je n'ai pas compris ce que tu cherches exactement, un algorithme pour générer toutes ces combinaisons ? ou juste savoir combien il y en a ? ou autre ?
Bonne journée
tamalou
les 2 du coup :)
Mais surtout savoir comment générer toutes les combinaisons , toutes les possibilités !
pour chaque combinés de 4 resultats toutes les possiblités pour 00 01 02 21 20 11 12 22 mais sur 4 combinés comme suit :
00 00 00 00
00 00 00 01
00 00 00 02
00 00 00 11
00 00 00 22
00 00 00 21
00 00 00 12
Invite
Message de Glozi (sans compte)
Si tu cherches un algorithme je te propose de méditer sur la manière dont nous écrivons nos nombres :
pourquoi $10$ après $9$ pourquoi $100$ après $99$ etc... (indice voir $99$ comme $099$ et voir $9$ et $10$ comme $009$ et $010$ si tu cherches les combinaisons à $3$ chiffres).
Cela devrait également te permettre de savoir combien il y a de combinaisons au total en réfléchissant un petit peu. (si tu veux un indice : tu peux te demander combien il y a de possibilité pour le premier chiffre, combien pour le deuxième etc...)
Bonne journée
yoshi
Ave,
Pour 1,3,5, c'est cela que tu cherches ?
11 11 11 11
11 11 11 13
11 11 11 15
11 11 11 31
11 11 11 33
11 11 11 35
11 11 11 51
11 11 11 53
11 11 11 55
Je pense que non, que cela doit continuer ensuite en remplaçant un ou plusieurs groupes 11 et en repartant du début... Non ?
Sinon, je ne vois pas et j'ai besoin de plus d'informations.
Parce que cela ne m'a pris qu'une minute à programmer en Python...
En plus, je vois que dans ta 4e colonne, ne figurent pas 10 et 20, normal ?
@+
tamalou
salut et merci pour ta reponse , oui exactement , mais pour chaque positions dans les 4 combinaisons de chiffre , pas seulement inverser les 2 derniers chiffres mais sur toutes les positions, toutes les possibilités de combinaisons avec
00 00 00 00
00 00 00 01
00 00 00 02
00 00 00 11
00 00 00 22
00 00 00 21
00 00 00 12
soit 11 11 11 11 ou 11 12 11 11 etc etc etc :)
yoshi
RE,
Désolé, Glozi a l'air d'avoir compris du 1er coup, moi je ne suis pas plus avancé !
Je t'ai fait remarquer que je ne voyais, dans ta 4e colonne ni 10, ni 20. Je repose ma question : normal ?
Qu'est ce qui viendrait après cette ligne :
00 00 00 00 ?
après cette-ci :
00 00 00 22 ?
Parce que
soit 11 11 11 11 ou 11 12 11 11 etc etc etc :)
ça ne me "parle" pas :-((
Tu veux des
combinaisons as-tu écrit...
Un module spécifique de Python me propose :
product (produit scalaire)
et de longueur de mon choix (j'ai choisi 2) :
permutations
combinations
combinations_w ith_replacement
J'ai testé les 4, rien ne colle avec ta demande...
Je nage complètement.
@+
tamalou
oui moi aussi ca me retourne le crâne :)
enfaite cest sur un pari sportif ,score exacte sur 4 matchs combinés : toutes les possibilités de score de 0-0 a 2-2 mais avec toutes les variables aussi comme 1-1 ou 2-1 et tout ca en combinants les matchs
Donc sur les 4 matchs combinés cela pourrait être par exemple : 0-0 ; 0-1 ; 2-2 ; 1-1
ou bien : 0-1 ; 2-2 ; 0-0 ; 1-2
et je veux donc savoir toutes les combinaisons possibles de cela :)
Merci à vous pour le temps que vous consacrez à essayer de m'aider :)
Invite
Message de Glozi (sans compte)
Bonsoir
Ce que j'essaie de t'expliquer c'est qu'il y a un ordre logique pour énumérer toutes les combinaisons possibles. Plus précisément, il existe un algorithme qui à partir d'une certaine combinaison te donne la suivante. Oublie pour le moment le fait que ce sont les résultats de matchs sportifs et essaye de voir les 8 chiffres simplement comme une suite ordonnée de symboles $0$ de $1$ et de $2$.
Par exemple est une telle suite de $8$ symboles $2 0 1 1 0 2 2 0$
Imagine qu'une telle combinaison représente un nombre (une quantité). Nous on compte habituellement en base $10$ cela signifie que pour écrire nos nombres nous avons $10$ symboles appelés chiffres, ce ont les biens connus $0,1,2,3,4,5,6,7,8,9$. À partir de ces chiffres nous pouvons écrire des nombres, et dans notre cas typiquement des entiers naturels.
On commence par $0$, puis $1$ puis $2$ puis ... puis $9$. Mince on est coincé, on a utilisé tous nos chiffres ! Qu'à cela ne tienne, le suivant sera $10$ (un $1$ puis un $0$). Autrement dit le chiffre des unités continue de boucler : après $9$ on remet $0$. Mais pour ne pas retomber sur nos pattes (on a déjà énuméré le nombre $0$) alors on rajoute le plus petit chiffre possible devant : à savoir le chiffre $1$. Ce qui donne $1$ et $0$. Attention on pourrait être tenté d'écrire $00$ au lieu de $10$ mais par convention on peut rajouter autant de fois le chiffre $0$ à gauche de notre écriture de notre nombre sans le changer (c'est bien pratique par ailleurs ainsi $00=0=00000000$ et $00001=1$).
Une fois qu'on est à $10$ on retourne à notre boucle et on rajoute $1$ au chiffre des unités. $11$, $12$... jusqu'à $19$. Bim le même problème ! On remplace $9$ par $0$ mais il faut ajouter $1$ (une retenue) au chiffre des dizaines... Quand on arrive à $99$ on ajoute $1$ au unité aux chiffres des unités : on obtiendra $0$ comme chiffre des unités. Mais on a une retenue, il faut la rajouter aux chiffres des dizaines qui est $9$ : on obtiendra $0$ pour le chiffre des dizaines, mais on a une retenue pour le chiffre des centaines, bref on obtient $100$.
Cette explication est assez triviale et longue pour peut être pas grand chose (je pense que tu sais très bien compter) mais comprendre "l'algorithme" caché derrière peut être utile pour ton problème :
En effet, dans ton cas tu as seulement trois chiffres et non plus dix, tu as seulement $0,1,2$. Tu ne peux donc écrire des nombres qu'avec ces trois chiffres. Si tu veux écrire des nombres à $8$ chiffres. Alors le premier sera $00000000$ puis $00000001$ puis $00000002$ puis $00000010$ (on a une retenue !) puis $00000011$ puis ...
Cela s'appelle compter en base $3$ (car seulement trois chiffres)
Bonne chance
yoshi
Bonsoir,
Merci à vous deux...
J'ai exactement 6561 lignes de 4 colonnes.
Avec le code suivant :
from itertools import product
L=list(product('012', repeat=8))
P=[[a+'-'+b,c+'-'+d,e+'-'+f,g+'-'+h] for a,b,c,d,e,f,g,h in L]
for P_i in P[:50]: # Affichage des 50 premier résultats
for score in P_i:
print (score,end=" ")
print()
Voici les 50 premières :
0-0 0-0 0-0 0-0
0-0 0-0 0-0 0-1
0-0 0-0 0-0 0-2
0-0 0-0 0-0 1-0
0-0 0-0 0-0 1-1
0-0 0-0 0-0 1-2
0-0 0-0 0-0 2-0
0-0 0-0 0-0 2-1
0-0 0-0 0-0 2-2
0-0 0-0 0-1 0-0
0-0 0-0 0-1 0-1
0-0 0-0 0-1 0-2
0-0 0-0 0-1 1-0
0-0 0-0 0-1 1-1
0-0 0-0 0-1 1-2
0-0 0-0 0-1 2-0
0-0 0-0 0-1 2-1
0-0 0-0 0-1 2-2
0-0 0-0 0-2 0-0
0-0 0-0 0-2 0-1
0-0 0-0 0-2 0-2
0-0 0-0 0-2 1-0
0-0 0-0 0-2 1-1
0-0 0-0 0-2 1-2
0-0 0-0 0-2 2-0
0-0 0-0 0-2 2-1
0-0 0-0 0-2 2-2
0-0 0-0 1-0 0-0
0-0 0-0 1-0 0-1
0-0 0-0 1-0 0-2
0-0 0-0 1-0 1-0
0-0 0-0 1-0 1-1
0-0 0-0 1-0 1-2
0-0 0-0 1-0 2-0
0-0 0-0 1-0 2-1
0-0 0-0 1-0 2-2
0-0 0-0 1-1 0-0
0-0 0-0 1-1 0-1
0-0 0-0 1-1 0-2
0-0 0-0 1-1 1-0
0-0 0-0 1-1 1-1
0-0 0-0 1-1 1-2
0-0 0-0 1-1 2-0
0-0 0-0 1-1 2-1
0-0 0-0 1-1 2-2
0-0 0-0 1-2 0-0
0-0 0-0 1-2 0-1
0-0 0-0 1-2 0-2
0-0 0-0 1-2 1-0
0-0 0-0 1-2 1-1
Et des 50 dernières :
2-2 2-2 1-0 1-1
2-2 2-2 1-0 1-2
2-2 2-2 1-0 2-0
2-2 2-2 1-0 2-1
2-2 2-2 1-0 2-2
2-2 2-2 1-1 0-0
2-2 2-2 1-1 0-1
2-2 2-2 1-1 0-2
2-2 2-2 1-1 1-0
2-2 2-2 1-1 1-1
2-2 2-2 1-1 1-2
2-2 2-2 1-1 2-0
2-2 2-2 1-1 2-1
2-2 2-2 1-1 2-2
2-2 2-2 1-2 0-0
2-2 2-2 1-2 0-1
2-2 2-2 1-2 0-2
2-2 2-2 1-2 1-0
2-2 2-2 1-2 1-1
2-2 2-2 1-2 1-2
2-2 2-2 1-2 2-0
2-2 2-2 1-2 2-1
2-2 2-2 1-2 2-2
2-2 2-2 2-0 0-0
2-2 2-2 2-0 0-1
2-2 2-2 2-0 0-2
2-2 2-2 2-0 1-0
2-2 2-2 2-0 1-1
2-2 2-2 2-0 1-2
2-2 2-2 2-0 2-0
2-2 2-2 2-0 2-1
2-2 2-2 2-0 2-2
2-2 2-2 2-1 0-0
2-2 2-2 2-1 0-1
2-2 2-2 2-1 0-2
2-2 2-2 2-1 1-0
2-2 2-2 2-1 1-1
2-2 2-2 2-1 1-2
2-2 2-2 2-1 2-0
2-2 2-2 2-1 2-1
2-2 2-2 2-1 2-2
2-2 2-2 2-2 0-0
2-2 2-2 2-2 0-1
2-2 2-2 2-2 0-2
2-2 2-2 2-2 1-0
2-2 2-2 2-2 1-1
2-2 2-2 2-2 1-2
2-2 2-2 2-2 2-0
2-2 2-2 2-2 2-1
2-2 2-2 2-2 2-2
Ça m'a bien l'air de coller...
@+
Invite
Message de Glozi (sans compte)
Très joli Yoshi ! La syntaxe de python permet de faire des miracles en si peu de lignes !
Pour ma part j'ai davantage l'habitude d'écrire du long code quitte à parfois (souvent) réinventer la roue. Mais ça me permet de bien comprendre ce que va faire le programme (et au passage ça me donne aussi une idée de la complexité temporelle/spatiale du programme). Ici si on lit le code à la vite on dirait que les initialisations de L ou de P sont rapides (c'est une ligne d'instruction pour chacune des deux variables quoi !) alors que c'est ce qui coute le plus de temps et d'espace !
Bonne soirée
yoshi
RE,
Merci.
J'ai réfléchi dans mon lit, hier soir, pour confirmer les 6561 Je m disais : pourquoi 6561 ?...
On commence à 00000000 et on finit à 22222222, en base 3.
$22222222=3^7\times 2+3^6\times 2+3^5\times 2+3^4\times 2+3^3\times 2+3^2\times 2+3^1\times 2+3^0\times 2$
D'où
$22222222= 2(3^7+3^6+3^5+3^4+3^3+3^2+3^1+3^0)$
Et la parenthèse est la somme des termes d'une suite géométrique de premier terme 1 (i.e :$3^0$) et de raison 3.
On trouve 6560 auquel j'ajoute 1, la ligne de zéros...
Toutes ces précisions pour tamalou).
----------------------------------------------
Je savais qu'il fallait fouiller dans le module itertools.
Et quand j'ai eu le fin mot de l'histoire, je suis retourné dans le module et j'ai relu :
product('ABCD', repeat=2) ---------------------> AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD
Ça c'est le produit scalaire de $\{A,B,C,D\}$ par lui -même...
Sauf que je n'ai pas réussi à obtenir la sortie annoncée, tout au plus, ai-je réussi à obtenir une liste à partir du générateur product...
Puis j'ai vu :
product(range(2),repeat=3) et obtenu :
[(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)]
J'ai essayé
list(product("01", repeat =3)) :
[('0', '0', '0'), ('0', '0', '1'), ('0', '1', '0'), ('0', '1', '1'), ('1', '0', '0'), ('1', '0', '1'), ('1', '1', '0'), ('1', '1', '1')]
Et j'avais pu constater que c'était la bonne piste et que de plus, le commentaire vu hier soir (et que je n'ai pas retrouvé ce matin) était exact : les résultats sont classés...
Après, ça n'était plus que du tripatouillage classique pour obtenir la sortie voulue...
L étant une liste d'octuplets, j'ai dû utiliser une liste supplémentaire P composés de sous listes regroupant les éléments des octuplets 2 par 2 en 4 chaînes.
Ne restait plus que l'affichage...
J'ai juste un peu "cabotiné" en utilisant une création de P par la méthode de "list comprehension" (bon j'ai aussi gagné deux lignes...).
Je me demande si cette discussion a bien sa place dans l'Entraide (Supérieur) : rien d'Enseignement Supérieur là-dedans, tout au plus Café Mathématique...Je laisse mûrir un peu et je déplace éventuellement.
@tamalou
Si ça te va, je peux enregistrer les 6561 lignes dans un fichier en .txt, que tu pourras ouvrir dans ton logiciel de Traitement de textes favori et que je t'enverrais par mail. La messagerie utilisée ne sera pas très rapide à la distribution : sa réception ne sera pas instantanée après l'envoi...
Mais, je voudrais quand même trouver un moyen d'automatiser, avec tes moyen,s d'autres "calculs" de ce type : déjà, ces 6561 lignes ne s'établissent pas d'un claquement de doigts.
Pour Python, là j'ai dû prendre une poignée de minutes (toujours moins que de créer les 65361 lignes à la main ^_^)
Le script Python a affiché ensuite (c'est ce qui prend le plus de temps) les 6561 lignes sans délai...
@+
Invite
Message de Glozi (sans compte)
Bonjour,
Autre façon de voir 6561
Simplement en utilisant le lemme des bergers : 3 choix pour le premier chiffre, 3 choix pour le deuxième etc...
Soit 3^8 = 6561 possibilités (car on considère des séquences avec 8 chiffres).
La création de $L$ coùte à mon avis $6561$ opérations.
La création de $P$ coute également $6561$ opérations.
Si tu affiches toutes les combinaisons alors cela coute également $6561$ opérations.
En revanche si tu affiches seulement les 50 premières et les 50 dernières alors cela ne coute que $100$ opérations.
Le fait que l'affichage est le plus long vient surement du fait que la commande $print" est assez longue.
En revanche si tu prend un alphabet à $26$ lettres ou sinon des mots de longueur $100$. Alors je ne pense pas que python arrive à générer $P$ ou $L$ ou alors ça va prendre beaucoup de temps.
Aussi on ne parle pas de l'espace mais le code que tu proposes ne pourrait clairement pas fonctionner sur ma machine à calculer programmable à cause d'un manque notable de RAM. Tu stockes en effet dans la RAM les 6561 listes de 8 chiffres (ça prend un peu de place !)
je propose le code suivant qui ne gagne pas en complexité temporelle mais en complexité spatiale.
def suivant(L,base):#version impérative
"""Prend une liste L qui comporte des chiffres entre 0 et base-1
L[0] représente le chiffre des unités
L[1] le chiffre des "dizaines" etc...
Renvoie la liste correspondant au nombre représenté par L incrémenté de $1$
Si ce n'est pas possible d'écrire le nombre suivant avec le même nombre de caractère qu'il y a dans L, alors envoie None
"""
retenue = True
i=0
while retenue and i< len(L):
if L[i]==base -1: #on garde la retenue
L[i]=0
else: #il n'y a plus de retenue
L[i]+=1
retenue = False
i+=1
if retenue: #s'il reste une retenue à la fin alors c'est qu'on était au max
return None
else:
return L
def suivant_rec(L, base): #version récursive
"""Prend une liste L qui comporte des chiffres entre 0 et base-1
L[0] représente le chiffre des unités
L[1] le chiffre des "dizaines" etc...
Renvoie la liste correspondant au nombre représenté par L incrémenté de $1$
Si ce n'est pas possible d'écrire le nombre suivant avec le même nombre de caractère qu'il y a dans L, alors envoie None
"""
if L == [base-1 for i in range(len(L))]: #si on est au max on renvoie None
return None
if L[0] < base-1: #si on peut rajouter une unité sans retenue on le fait.
L[0] +=1
return L
else:
M = suivant_rec(L[1:],base) #on rajouter une retenue (elle pourrait se propager donc on fait une récurrence)
return [0]+M #on remet l'unicité à 0
def afficher(L):
"""Une fonction qui affiche la liste (dans l'ordre inverse pour que ça soit plus joli)"""
for i in range(len(L)-1,-1,-1):
print(L[i],end= " ")
print()
base = 3
longueur = 8
L = [0 for i in range(longueur)]
n=0 # un compteur qui va compter le nombre de combinaisons
while L is not None:
n+=1
afficher(L)
L=suivant(L, base) #on passe à la suite suivante (cela renvoie None si on était déjà à la dernière liste)
print("il y a ",n,"combinaisons")
print("il y a en effet", base**longueur, "combinaisons") #on pouvait savoir le nombre de combinaisons avec cette formule.
Il a deux versions pour la fonction $suivant$ (récursif ou impératif).
Bonne journée
yoshi
Re,
Ah, pour prendre de l'espace, ça en prend : quel courage d'avoir pondu ça !
Et "
C'est beau comme l'antique !"...
Du coup, je vais aussi chercher une méthode de remplissage à moi...
Oui, j'ai pas mal de RAM installée : 16 Go...
Je suis finalement allé chercher bien loin pour 6561 : je n'avais jamais entendu l'expression "lemme des bergers", alors que c'est si simple à utiliser... et que pour d'autre exos, je l'ai déjà employé, mais là, ça ne m'est pas venu à l'esprit.
Je pense d'abord à ce qui est compliqué et "tordu" (je me prends régulièrement en flagrant délit, aussi - en principe - je me méfie : ça amusait beaucoup ma Prof en Math Elem, moins mes voisin(e)s.
Si tu affiches toutes les combinaisons alors cela coute également 6561 opérations.
Bin non, parce que je ne peux pas ; l'IDLE de Python refuse de m'afficher les 6561 lignes : ça fait trop...
@+
Invite
Message de Glozi (sans compte)
Bonsoir,
Il m'est venu une méthode un peu alternative (avec du récursif) mais qui est grosso modo la même que précédemment (j'évite juste l'utilisation des listes, au profit des chaines de caractères...)
def sequence_rec(longueur,base, prev=""):
if longueur == 0:
print(prev)
return
else:
for i in range(base):
sequence_rec(longueur-1,base,prev+str(i)+(" " if longueur >1 else ""))
sequence_rec(8,3)
Pour ma part j’utilise jupyter notebook (je crois qu'il était inclus dans Anaconda) pour coder avec python et je n'ai pas de soucis pour avoir les 6561 lignes affichées.
Bonne soirée
tamalou
Bonjour :D
Je vois que vous vous eclatez ! :)
C'est très intéressant ce que vous faites même si je suis très vite largué !
@yoshi oui , je veux bien ca serait super sympa de ta part si tu voudrais bien m'envoyer la même chose pour 00 00 et 00 00 00 et du coup 00 00 00 00 ? Si ce n'ai pas trop couteux pour toi en temps ou autre ?
Merci beaucoup
yoshi
Re,
la même chose pour 00 00 et 00 00 00 et du coup 00 00 00 00
En tournant toujours avec 0,1,2 ?
Je vais essayer de trouver du temps...
Parce que j'ai une revue de 20 pages sur les bras et j'ai 3 semaines de retard...
Du coup, je fais quoi des tirets ? tu les veux ou pas ?
Mon programme s'adapte très facilement à 4 et à 6.
il suffit que je remplace repeat =8 par respectivement repeat=4 et repeat =6 et qu'au lieu d'utiliser a,b,c,d,e,f,g,h je me limite à
a,b,c,d pour 00 00
a,b,c,d,e,f pour 00 00 00
L'idéal serait peut-être que je te crée plutôt que des fichiers en .txt, des fichiers en .csv que tu ouvrirais directement avec Excel (ou compatible comme OpenOffice ou LibreOffice par ex) ?
@Glozi
Pas de message d'erreur pour la pile avec la récursivité ?
@+
Invite
Message de Glozi (sans compte)
Yoshi, en tout cas je peux aller à 8 de profondeur en récursivité sans problème, mais ça renvoie une erreur pour toi ?
Bonne soirée
yoshi
Non, pas testé...
Mais c'est un problème connu...
Peut-être que Jupyter, sans le dire, gère la pile à la volée ?
Que Morphée se montre accueillante avec toi !
Invite
Message de Glozi (sans compte)
Bonsoir,
La limite de profondeur pour la récursivité en python est de 1000 par défaut selon un post de Stack overflow (le site m’empêche de poster un lien vers le post précis ?) du coup pour des mots de 8 chiffres on n'a aucun soucis (et ça devrait prendre beaucoup moins de place en mémoire que de stocker toutes les combinaisons possibles).
Bonne nuit également !