Il nous est demandé de trouver le nombres de chiffres différents que nous pouvons trouver dans n arrays en prenant UN seul élément par array. Par exemple :
En input nous avons :
[[1],
[2,3,1],
[3,4,5],
[2,1,4],
[2,3]]
Et en output, nous sommes censés avoir : 5 (si on retire le [2,3], la réponse passe à 4)
Dans les faits c'est simple mais je ne trouve pas d'algorithme viable. Au début, je fais en sorte de prendre les arrays de taille unitaire et prend leur valeur. Je pensais aussi prendre les nombres qui apparaissent une fois. Mais je bloque vraiment si on nous donne un gros input, je ne vois pas comment faire pour qu'il regarde toutes les possibilités avant de trouver le résultat sans faire de boucle infini ou autre.
Si quelqu'un peut m'éclairer, me donner une direction ou un pseudo code ce serait top !
Effectivement, il s'agit du nombre maximale de chiffre différent en se limitant à un chiffre par array !
Et par "gros" je parle d'array avec plus d'éléments (dans mon exemple je les ai limité à 3). Je n'arrive pas à trouver un algorithme qui cherchera le meilleur chiffre dans chacun des sous array.
Je ne suis pas certain de comprendre ton problème. Si tu te faisais un dictionnaire en donnant le nombre comme clé et comme valeur la fréquence. Il faut vérifier au départ que la clé existe. Que veut dire "en prenant un seul élément par array"? Si j'ai [1,2,1] le 1 est compté une seule fois, c'est bien ça? Dans ce cas, je parcours chaque array (ou liste( et je met chaque élément dans un set. À la fin, je prend la longueur du set avec len().
Le Tout est souvent plus grand que la somme de ses parties.
Un seule élément par sous array signifie que pour chacun je ne peux en prendre qu'un par exemple un cas de résolution de mon problème est :
[[1], -> Je prends le 1
[2,3,1], -> Je prends le 3
[3,4,5], -> Je prends le 5
[2,1,4], -> Je prends le 4
[2,3]] -> Je prends le 2
Et oui il faut des chiffres différents donc avoir [1,2,1] est inutile. (1 sera compté que 1 fois)
ET si par exemple, on retire le [2,3], on pourra prendre que 4 chiffres différents maximales donc tout parcourir et mettre dans un set ne va pas fonctionner.
Sortir le plus de nombres dépendra du nombre d’occurrence des différents nombre dans chaque liste. Par exemple, 5 n’apparaissant que dans la liste [3,4,5], si on ne le prends pas, il est perdu alors que 4 et 3 apparaissent dans d'autres listes.
D'où l'idée d'associer à chaque nombre, la liste des indices où il est présent et la ranger par ordre croissant de la longueur des listes.
Ce qui donne une liste L de tuple de la forme [ (5, [2]), (4: [2, 3]),... ] et une liste de positions P à effacer.
On parcourt L avec une boucle où à chaque itération, le premier item le nombre à choisir et le deuxième une liste des indices.
Si on trouve un indice à effacer, on le supprime de P et on garde le nombre.
La difficulté est de montrer que ce genre d'algorithme trouve toujours la meilleure solution... (ou un contre exemple montrant que çà ne marche pas dans tous les cas).
De ce que je comprends de la question et de l'exemple de réponse, je dirais qu'il faut trouver simplement le nombre d'éléments dans la liste (un équivalent à len(liste), donc pour chaque élément de la liste, j'incrémente un compteur. (après il faut peut-être vérifier que l'élément est une liste et non vide ?)
De ce que je comprends de la question et de l'exemple de réponse, je dirais qu'il faut trouver simplement le nombre d'éléments dans la liste (un équivalent à len(liste), donc pour chaque élément de la liste, j'incrémente un compteur. (après il faut peut-être vérifier que l'élément est une liste et non vide ?)
Non cela ne va pas fonctionner, comme dit précédemment si on retire le [3,2], la solution passera à 4 tandis que votre compteur va quand même sortir un 5.
La difficulté est de montrer que ce genre d'algorithme trouve toujours la meilleure solution... (ou un contre exemple montrant que çà ne marche pas dans tous les cas).
Oui et votre algorithme ne sortira pas à chaque fois la meilleure solution :/ Cet algo fait parti de mes échecs d'hier haha ...
(Mon autre compte NoNameAgain a été bloqué pour 24h (la raison ??), j'ai donc changé de compte ...)
La difficulté est de montrer que ce genre d'algorithme trouve toujours la meilleure solution... (ou un contre exemple montrant que çà ne marche pas dans tous les cas).
Oui et votre algorithme ne sortira pas à chaque fois la meilleure solution :/ Cet algo fait parti de mes échecs d'hier haha ...
si en input nous avons des arrays plus grand que 3 avec chaque chiffres dans plusieurs tableaux comme ceci [ (5, [2,3,7]), (4: [2,3,5]),... ], votre algorithme ne sera pas lequel supprimer étant donné qu'il n'y en a aucun "à effacer"
Sinon je ne pense pas que ton compte soit bloqué, mais on ne peut pas poster 2 réponses successives sauf si il y a un délai de 24h sans réponses entre temps.
Merci à tous, j'avais droit à une complexité temporelle de O(n^3) donc je me suis pas gêné et j'ai bêtement fait un algo qu'il testait toutes les possibilités.
si en input nous avons des arrays plus grand que 3 avec chaque chiffres dans plusieurs tableaux comme ceci [ (5, [2,3,7]), (4: [2,3,5]),... ], votre algorithme ne sera pas lequel supprimer étant donné qu'il n'y en a aucun "à effacer"
Je choisis 5 et j'efface 2: je choisis le 5 de la 3ème ligne.
Puis je choisi 4 et j'efface 3: je choisis le 4 de la 4ème ligne (la troisième ayant été utilisée/effacée)
Je ne vois pas en quoi cela est un contre-exemple.
(ce qui ne veut pas dire qu''il n'y ait pas de contre exemples, juste que j'ai la flemme de passer du temps à le trouver et à démontrer que l'algorithme trouvera toujours la plus grande liste de...)
@mps: Moi aussi, j'avais la flemme de coder ... Voici tout de même la liste complète des tuples: [(5, [2]), (4, [2, 3]), (1, [0, 1, 3]), (2, [1, 3, 4]), (3, [1, 2, 4])] Ta liste de tuples pourrait être associée à une liste de choix pour chaque nombre. Par exemple, si tu commences par 5, il n'a qu'un choix, c'est 2. Donc tu places le 2 en première position (la même que le 5) Donc, [2, 3, 0 ...] qui sont les premiers choix pour 5, 4, 1, ... En passant au nombre suivant, tu regardes si son premier choix est déjà dans la liste des choix. Si ça bloque en quelque part, tu reviens en arrière en choisissant l'indice suivant pour ce nombre. Si c'est le dernier, tu recules au nombre précédent et tu prend son choix suivant, etc. C'est un arbre de décisions avec backtracking. Il va de soi que le nombre de chiffres différents est au maximum égal au nombre de listes dans l'array (ou d'array dans la liste ...) Les objets dans ces array pourraient être autre chose que des chiffres.
Le Tout est souvent plus grand que la somme de ses parties.
Je me suis décidé à coder l'algo. Pas trop compliqué. Mon accès au bouton <code> l'est bien plus. En affichant les solutions, j'en ai trouvé 2 qui donnent 5 chiffres. Je dois passer par un dictionnaire pour obtenir la liste proposée par mps. Puisque la nature des objets n'a pas d'importance, je les ai tout simplement éliminés. Cela simplifie le code. - #*# Nombre de chiffres différents dans N array. #*array=[[1], [2,3,1], [3,4,5], [2,1,4], [2,3]] #*dico={} #*for l in range(len(array)): #* for c in array[l]: #* if c not in dico.keys(): #* dico[c]=[] #* dico[c].append(l) #*liste=sorted([v for k,v in dico.items()],key=lambda v: len(v)) #*# chercher le nombre de chiffres. #*i=0 #*c=0 #*arbre=[] #*mx=0 #*nMax=0 #*while i>=0: #* while c<len(liste[i]): #* if liste[i][c] in arbre: #* c+=1 #* else: #* mx+=1 #* arbre.append(liste[i][c]) #* i+=1 #* c=0 #* if i>=len(array): #* if mx>nMax: nMax=mx #* c=arbre.pop()+1 #* i-=1 #* mx-=1 #* # backtracking #* while i>0: #* i-=1 #* c=arbre.pop()+1 #* mx-=1 #* if c<len(liste[i]): break #* if i==0: i=-1 # Il ne reste plus d'alternative. #*# Solution. #*print(nMax)
Le Tout est souvent plus grand que la somme de ses parties.
Nombre de chiffres différents dans N array
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Découverte Python Doc Tkinter Les chaînes de caractères
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.