Reduction de liste de nombre
benoitdunord
-
KX Messages postés 16761 Date d'inscription Statut Modérateur Dernière intervention -
KX Messages postés 16761 Date d'inscription Statut Modérateur Dernière intervention -
bonjour,
pour commencer, comme je ne m'y connait pas en creation de programme ou de logiciel, je ne sais pas s'il y a une réponse à ma question
voila mon cas
j'ai plusieurs listes de nombres (une dizaine de listes avec chacune une dizaine de nombres; toutes les listes ont le meme nombre de nombres)
un meme nombre peut se trouver dans plusieurs listes mais dans chaque liste il n'y a qu'une fois chaque nombre
J'aimerais avoir un programme qui me permette, apres que j'ai inscrit toutes mes listes de nombres, d'obtenir une serie de 5 nombres sachant que chacune des séries initales doit contenir au moins un des numéro de la serie finale.
je vais expliquer par un petit exemple:
si j'avais 3 series de nombres et que je veux recuperer 2 nombres:
1- 6 7 8
2-1 2 3
3-1 4 7
je pourrais prendre 1 et 6, car je prends dans les 3
Mais je ne peux avoir 6 et 3 car là je ne prends rien dans la 3ème
Là c'etait un cas simple mais dans mon cas je veux 5 nombres et j'ai une dizaine de listes contant chacune une dizaine de nombres
Je sais ce n'est pas tres clair mais je ne sais pas comment mieux expliquer.
Cependant, j'essauerais de répondre à toutes les questions.
Merci d'avance aux personnes qui vont m'aider
pour commencer, comme je ne m'y connait pas en creation de programme ou de logiciel, je ne sais pas s'il y a une réponse à ma question
voila mon cas
j'ai plusieurs listes de nombres (une dizaine de listes avec chacune une dizaine de nombres; toutes les listes ont le meme nombre de nombres)
un meme nombre peut se trouver dans plusieurs listes mais dans chaque liste il n'y a qu'une fois chaque nombre
J'aimerais avoir un programme qui me permette, apres que j'ai inscrit toutes mes listes de nombres, d'obtenir une serie de 5 nombres sachant que chacune des séries initales doit contenir au moins un des numéro de la serie finale.
je vais expliquer par un petit exemple:
si j'avais 3 series de nombres et que je veux recuperer 2 nombres:
1- 6 7 8
2-1 2 3
3-1 4 7
je pourrais prendre 1 et 6, car je prends dans les 3
Mais je ne peux avoir 6 et 3 car là je ne prends rien dans la 3ème
Là c'etait un cas simple mais dans mon cas je veux 5 nombres et j'ai une dizaine de listes contant chacune une dizaine de nombres
Je sais ce n'est pas tres clair mais je ne sais pas comment mieux expliquer.
Cependant, j'essauerais de répondre à toutes les questions.
Merci d'avance aux personnes qui vont m'aider
A voir également:
- Reduction de liste de nombre
- Liste déroulante excel - Guide
- Nombre de jours entre deux dates excel - Guide
- Liste déroulante en cascade - Guide
- Liste de diffusion whatsapp - Guide
- Meilleur site de coupon reduction - Guide
5 réponses
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
benoitdunord
dans mon cas, certains nombres peuvent se trouver dans plusieurs listes
KX
Messages postés
16761
Date d'inscription
Statut
Modérateur
Dernière intervention
3 020
C'est bien le problème, ils peuvent, mais ce n'est pas certain !
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...
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 ^^)
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 :(
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
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";}
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...
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
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.
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