Reduction de liste de nombre
Fermé
benoitdunord
-
28 juin 2011 à 14:13
KX Messages postés 16753 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 - 30 juin 2011 à 14:05
KX Messages postés 16753 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 - 30 juin 2011 à 14:05
A voir également:
- Reduction de liste de nombre
- Liste déroulante excel - Guide
- Bon de reduction - Guide
- Liste déroulante en cascade - Guide
- Liste de diffusion whatsapp - Guide
- Liste de numéro de téléphone suspect - Guide
5 réponses
KX
Messages postés
16753
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
25 novembre 2024
3 019
28 juin 2011 à 14:40
28 juin 2011 à 14:40
Tu auras des cas impossibles...
Le plus évident à montrer c'est s'il n'y a pas de doublons dans tes listes.
Exemple avec 6 listes et autant de nombres que tu veux dedans :
Tu ne peux pas trouver cinq nombres tels que chacune de ces six listes contiennent au moins un de ces nombres. En fait tu auras le problème à chaque fois que tu chercheras N nombres avec M listes si M>N, or c'est ton cas vu que N=5, et M=une dizaine
Le plus évident à montrer c'est s'il n'y a pas de doublons dans tes listes.
Exemple avec 6 listes et autant de nombres que tu veux dedans :
0- 0, 6, 12... 6k... 1- 1, 7, 13... 6k+1... 2- 2, 8, 14... 6k+2... ... 5- 5, 11, 17... 6k+5...
Tu ne peux pas trouver cinq nombres tels que chacune de ces six listes contiennent au moins un de ces nombres. En fait tu auras le problème à chaque fois que tu chercheras N nombres avec M listes si M>N, or c'est ton cas vu que N=5, et M=une dizaine
anatolekadel
Messages postés
102
Date d'inscription
jeudi 26 mai 2011
Statut
Membre
Dernière intervention
18 novembre 2011
3
28 juin 2011 à 14:46
28 juin 2011 à 14:46
Salut, je pense qu'il doit bien y avoir un moyen en effet de récupérer tes chiffres.
Mais dis-nous en quel langage tu code ?
Si j'ai bien compris, tu souhaites avoir une liste de nombres qui sont tous présent dans tes listes. (dans ton exemple, il y aurait aussi 7 et 2, non ?).
Il suffirait donc de faire des test pour regarder quel nombres est présent dans plusieurs listes. Ensuite, tu met le tout dans un tableau, et tu refais les test pour au final obtenir tes 5 nombres... Mais, bon, si tu as une liste qui ne comporte aucun nombre présent dans les autres listes, elle ne sera pas reprise, donc il faut encore faire un test pour vérifier que tu pioche dans toutes tes listes...
Voilà un peu le truc; mais dis-nous en quelle langage il faut te répondre parce que certains langages acceptent ce que d'autre pas...
Mais dis-nous en quel langage tu code ?
Si j'ai bien compris, tu souhaites avoir une liste de nombres qui sont tous présent dans tes listes. (dans ton exemple, il y aurait aussi 7 et 2, non ?).
Il suffirait donc de faire des test pour regarder quel nombres est présent dans plusieurs listes. Ensuite, tu met le tout dans un tableau, et tu refais les test pour au final obtenir tes 5 nombres... Mais, bon, si tu as une liste qui ne comporte aucun nombre présent dans les autres listes, elle ne sera pas reprise, donc il faut encore faire un test pour vérifier que tu pioche dans toutes tes listes...
Voilà un peu le truc; mais dis-nous en quelle langage il faut te répondre parce que certains langages acceptent ce que d'autre pas...
anatolekadel
Messages postés
102
Date d'inscription
jeudi 26 mai 2011
Statut
Membre
Dernière intervention
18 novembre 2011
3
28 juin 2011 à 15:04
28 juin 2011 à 15:04
Et bien, oui, ça doit être faisable relativement facilement. Mais en quel langage serait-ce le plus simple ??? Je ne saurai pas te répondre, je ne connais pas tous les langages.
Mais maintenant, je ne sais pas trop si un programme similaire existe déjà. Sans doute que oui, mais où le trouver, là encore, je ne sais pas trop te diriger.
Si le PHP ne te rebute pas de trop, va voir du coté de PHPCS: https://codes-sources.commentcamarche.net/
Il y a parfois de belles surprises ^^
Et pour les cours : SDZ: https://openclassrooms.com/fr/
C'est LA référence pour les premiers pas (et même pour les seconds ^^)
Mais maintenant, je ne sais pas trop si un programme similaire existe déjà. Sans doute que oui, mais où le trouver, là encore, je ne sais pas trop te diriger.
Si le PHP ne te rebute pas de trop, va voir du coté de PHPCS: https://codes-sources.commentcamarche.net/
Il y a parfois de belles surprises ^^
Et pour les cours : SDZ: https://openclassrooms.com/fr/
C'est LA référence pour les premiers pas (et même pour les seconds ^^)
KX
Messages postés
16753
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
25 novembre 2024
3 019
28 juin 2011 à 15:29
28 juin 2011 à 15:29
Je ne vois pas trop pourquoi faire du PHP ici...
Un petit programme compilé genre Pascal (simple à comprendre, rapide à installer et utiliser) devrait faire l'affaire... je m'y pencherai peut-être dessus ce soir ou demain si c'est pas urgent, mais j'ai quand même quelques doutes car comme je l'ai montré tout à l'heure, ça peut ne pas marcher :(
Un petit programme compilé genre Pascal (simple à comprendre, rapide à installer et utiliser) devrait faire l'affaire... je m'y pencherai peut-être dessus ce soir ou demain si c'est pas urgent, mais j'ai quand même quelques doutes car comme je l'ai montré tout à l'heure, ça peut ne pas marcher :(
anatolekadel
Messages postés
102
Date d'inscription
jeudi 26 mai 2011
Statut
Membre
Dernière intervention
18 novembre 2011
3
28 juin 2011 à 16:41
28 juin 2011 à 16:41
Je ne code pas en Pascal, je ne sais donc pas si c'est mieux ou pas que le PHP pour ce genre d'applications.
Mais c'est vrai que ça peut ne pas marcher; il suffit donc, dans un premier temps de vérifier que dans liste, il y a au moins un nombre présent dans au moins une autre liste. Si oui, le programme se lance, si non, il affiche une erreur et puis voilà ;D
Mais c'est vrai que ça peut ne pas marcher; il suffit donc, dans un premier temps de vérifier que dans liste, il y a au moins un nombre présent dans au moins une autre liste. Si oui, le programme se lance, si non, il affiche une erreur et puis voilà ;D
Leviathan49
Messages postés
257
Date d'inscription
jeudi 10 juin 2010
Statut
Membre
Dernière intervention
22 juillet 2011
70
Modifié par Leviathan49 le 29/06/2011 à 09:30
Modifié par Leviathan49 le 29/06/2011 à 09:30
Ca se fait pas trop mal avec des expressions régulières. Ci dessous un exemple en perl.
Mais ça doit se faire sans trop de problème en php si besoin.
Mais ça doit se faire sans trop de problème en php si besoin.
#!/usr/bin/perl use strict; use warnings; #lignes à tester my $string ="0- 0, 6, 12 1- 1, 7, 13 2- 2, 8, 14 3- 1, 2, 3 4- 4, 5, 6 5- 5, 11, 17"; my @tab = split(/\n/,$string); # nombres a retrouver my @n = (1,2,3,5,12); my $pattern = "^([0-9])+[-].*[^0-9](".join('|',@n).")(?:,|\$)"; print "pattern:".$pattern."\n"; # 1 si une des nombre trouvé 0 sinon my $bool = 1; foreach(@tab) { if($_ !~ /$pattern/) {$bool = 0;} else {print "ligne $1 : $2 a ete trouve\n";} } if($bool) { print "OK\n";} else { print "FAIL\n";}
KX
Messages postés
16753
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
25 novembre 2024
3 019
29 juin 2011 à 10:56
29 juin 2011 à 10:56
Je ne connais pas le Perl mais j'ai l'impression que là tu pars du résultat (1,2,3,5,12) pour montrer qu'il est valide, mais tu ne fais pas vraiment la recherche sur les listes qui dit pourquoi c'est (1,2,3,5,12) que tu prends et pas un autre.... Comment tu choisis n ?
Leviathan49
Messages postés
257
Date d'inscription
jeudi 10 juin 2010
Statut
Membre
Dernière intervention
22 juillet 2011
70
Modifié par Leviathan49 le 29/06/2011 à 12:53
Modifié par Leviathan49 le 29/06/2011 à 12:53
Ah, tu dois trouver les 5 nombres...
Je pensais que tu les connaissait déjà et que tu voulais juste vérifier.
Du coup ça deviens plus compliqué.
Je ne vois même pas de solution simple d'ailleurs ^^"
A part tester par la force brute je vois pas...
Mais bon, pour les chiffres de 0 à 100 ca te donne 75 287 520 couples de 5 chiffres possibles...
Je pensais que tu les connaissait déjà et que tu voulais juste vérifier.
Du coup ça deviens plus compliqué.
Je ne vois même pas de solution simple d'ailleurs ^^"
A part tester par la force brute je vois pas...
Mais bon, pour les chiffres de 0 à 100 ca te donne 75 287 520 couples de 5 chiffres possibles...
KX
Messages postés
16753
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
25 novembre 2024
3 019
Modifié par KX le 29/06/2011 à 22:42
Modifié par KX le 29/06/2011 à 22:42
Voici ce que je propose, j'ai fait le code en Java.
Déjà tes "listes" sont en fait des ensembles (pas de doublon, et pas d'ordre)
Si tu prends un groupe d'ensemble, tu peux regarder quel est l'entier qui apparaît le plus souvent et dans ce cas tu sélectionnes cet entier, et tu supprimes tous les ensembles du groupe qui le possèdent. Et tu recommences jusqu'à avoir supprimer tous les ensembles, tu auras alors un ensemble d'entiers qui font ce que tu veux.
Si tu en as pas assez, tu en rajoutes comme tu veux, si tu en as trop par rapport au nombre que tu veux, c'est que pas possible...
Remarque : ça te donne une solution, mais si il y a égalité entre les max, par défaut on prend le premier, et c'est pas forcément la meilleure solution, mais c'est déjà pas mal...
Y a plus qu'à te mettre au Java pour comprendre ce que j'ai fait ;-)
La confiance n'exclut pas le contrôle
Déjà tes "listes" sont en fait des ensembles (pas de doublon, et pas d'ordre)
Si tu prends un groupe d'ensemble, tu peux regarder quel est l'entier qui apparaît le plus souvent et dans ce cas tu sélectionnes cet entier, et tu supprimes tous les ensembles du groupe qui le possèdent. Et tu recommences jusqu'à avoir supprimer tous les ensembles, tu auras alors un ensemble d'entiers qui font ce que tu veux.
Si tu en as pas assez, tu en rajoutes comme tu veux, si tu en as trop par rapport au nombre que tu veux, c'est que pas possible...
Remarque : ça te donne une solution, mais si il y a égalité entre les max, par défaut on prend le premier, et c'est pas forcément la meilleure solution, mais c'est déjà pas mal...
Y a plus qu'à te mettre au Java pour comprendre ce que j'ai fait ;-)
import java.util.HashMap; import java.util.HashSet; public class Test { public static void main(String args[]) { Groupe g = new Groupe(new Ensemble(6,7,8),new Ensemble(1,2,3),new Ensemble(1,4,7)); System.out.println(g.selectionner()); // {1,6} } } class Ensemble extends HashSet<Integer> { private static final long serialVersionUID = 1L; public Ensemble(int...entiers) { super(); for (int n : entiers) add(n); } public boolean contient(int n) { for (int i : this) if (i==n) return true; return false; } public String toString() { StringBuffer sb = new StringBuffer("{"); for (int i : this) sb.append(i+","); return sb.replace(sb.length()-1, sb.length(), "}").toString(); } } class Groupe extends HashSet<Ensemble> { private static final long serialVersionUID = 1L; public Groupe(Ensemble...ensembles) { super(); for (Ensemble e : ensembles) add(e); } public int max() { int m=0, n=-1; HashMap<Integer,Integer> h = new HashMap<Integer,Integer>(); for (Ensemble e : this) { for (Integer i : e) { if (h.containsKey(i)) h.put(i, h.get(i)+1); else h.put(i, 1); if (h.get(i)>m) { m=h.get(i); n=i; } } } return n; } public Groupe supprimer(int n) { Groupe g=new Groupe(); for (Ensemble e : this) if (!e.contient(n)) g.add(e); return g; } public Ensemble selectionner() { Ensemble e = new Ensemble(); Groupe g = new Groupe(); g.addAll(this); while (!g.isEmpty()) { int n=g.max(); e.add(n); g = g.supprimer(n); } return e; } public String toString() { StringBuffer sb = new StringBuffer("{"); for (Ensemble e : this) sb.append(e+","); return sb.replace(sb.length()-1, sb.length(), "}").toString(); } }
La confiance n'exclut pas le contrôle
Leviathan49
Messages postés
257
Date d'inscription
jeudi 10 juin 2010
Statut
Membre
Dernière intervention
22 juillet 2011
70
30 juin 2011 à 09:31
30 juin 2011 à 09:31
Le seul problème, c'est le cas :
0- 1,2,3
1- 2,3,4
2- 2,4,5,6
3- 2,5,6
4- 7
Vu que tu raisonne de manière statistique le programme te renverra les entiers 1,2,3,4,5,6,7 alors que 2 et 7 suffisent.
Enfin, bon, je cherche la petite bête là :p Avec des listes suffisamment remplie ça devrait marcher sans prob.
0- 1,2,3
1- 2,3,4
2- 2,4,5,6
3- 2,5,6
4- 7
Vu que tu raisonne de manière statistique le programme te renverra les entiers 1,2,3,4,5,6,7 alors que 2 et 7 suffisent.
Enfin, bon, je cherche la petite bête là :p Avec des listes suffisamment remplie ça devrait marcher sans prob.
KX
Messages postés
16753
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
25 novembre 2024
3 019
30 juin 2011 à 14:05
30 juin 2011 à 14:05
Non, avec mon code ton exemple renverra bien 2 et 7, car l'occurrence maximale est 2 (4 fois) donc on le choisit en premier; et en supprimant tous les ensembles qui contiennent 2 il ne restera plus que le 7
Voici un exemple qui marcherait mal : {{1,3,6},{1,2,7},{1,2,8},{1,2,9},{4,2,10},{5,3,11}}
L'occurrence maximale est 4, mais elle est atteinte par 1 et par 2 or mon algorithme choisira le 1.
Il restera alors {{4,2,10},{5,3,11}} une fois tous les ensembles contenant 1 supprimés.
Ça conduira donc finalement à obtenir {1,2,3} comme résultat.
Alors que si on avait d'abord choisit 2, il serait resté {{1,3,6},{5,3,11}}, et on aurai obtenu {2,3}
C'est un cas très particulier (j'ai eu du mal à trouver un exemple ^^) mais en général ça doit marcher plutôt pas mal. D'autant plus que le but final n'est pas de trouver le plus petit ensemble mais de trouver un ensemble de taille donnée, ici si on demandait un ensemble de taille 3 ou plus ça irait...
Voici un exemple qui marcherait mal : {{1,3,6},{1,2,7},{1,2,8},{1,2,9},{4,2,10},{5,3,11}}
L'occurrence maximale est 4, mais elle est atteinte par 1 et par 2 or mon algorithme choisira le 1.
Il restera alors {{4,2,10},{5,3,11}} une fois tous les ensembles contenant 1 supprimés.
Ça conduira donc finalement à obtenir {1,2,3} comme résultat.
Alors que si on avait d'abord choisit 2, il serait resté {{1,3,6},{5,3,11}}, et on aurai obtenu {2,3}
C'est un cas très particulier (j'ai eu du mal à trouver un exemple ^^) mais en général ça doit marcher plutôt pas mal. D'autant plus que le but final n'est pas de trouver le plus petit ensemble mais de trouver un ensemble de taille donnée, ici si on demandait un ensemble de taille 3 ou plus ça irait...
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
28 juin 2011 à 14:44
28 juin 2011 à 14:46