Reduction de liste de nombre

Fermé
benoitdunord - 28 juin 2011 à 14:13
KX Messages postés 16752 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 août 2024 - 30 juin 2011 à 14:05
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



5 réponses

KX Messages postés 16752 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 août 2024 3 018
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 :
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
0
benoitdunord
28 juin 2011 à 14:44
dans mon cas, certains nombres peuvent se trouver dans plusieurs listes
0
KX Messages postés 16752 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 août 2024 3 018
28 juin 2011 à 14:46
C'est bien le problème, ils peuvent, mais ce n'est pas certain !
0
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
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...
0
benoitdunord
28 juin 2011 à 14:53
tu as raison, dans mon exemple 2 et 7 fonctionnent aussi
Pour répondre à ta question, comme je ne m'y connait pas en programation, je ne sais pas comment faire pour resoudre mon probleme et c'etait pour savoir si un tel programme existait deja ou si c'etait facile de le fabriquer
0
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
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 ^^)
0
KX Messages postés 16752 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 août 2024 3 018
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 :(
0
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
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
0
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
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.
#!/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";}
0
KX Messages postés 16752 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 août 2024 3 018
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 ?
0
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
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...
0
KX Messages postés 16752 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 août 2024 3 018
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 ;-)

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
0
benoitdunord
29 juin 2011 à 22:40
merci à toi je vais tester
0
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
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
KX Messages postés 16752 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 31 août 2024 3 018
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...
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
benoitdunord
30 juin 2011 à 09:23
est ce que vous pensez qu'avec une macro excel ca peut fonctionner.
C'est juste une question, comme je ne m'y connait pas
0