Combinatoire et recherche

Version imprimable

03/10/2006, 04h53
zhao

Combinatoire et recherche

Bonjour a tous :salut:

voila j'ai un probleme de programmation mais je ne sais pas comment faire
:mur: je suis neophite en la matiere voila mon probleme .

comment programmer ceci en C .

dans un fichier j'ai des entiers ( 10 par ligne ) ex

1 2 3 4 5 6 7 8 9 10
1 2 5 7 9 10 11 13 14 15
.....
.....
.....
dans mon programme je genere toutes les combinaisons possibles
de 1 a 25 de 10 chiffres C ( 10 25 ) ce qui fait 3 268 760 combinaisons

chaque combinaisons generé doit etre verifier avec chaque ligne de mon fichier ( donc verifier chffre par chiffre) quand un chiffre est commun je doit incrementer un compteur ,faire cela jusqu'a la fin des combinaisons generées .

comment programmer ce genre de choses de façon a ce qu'il soit le plus optimiser possible ? ( par exemple les boucles imbriquées qui sont tres nombreuse , recursivité ... enfin bref je sais pas ;-) )

merci de votre aide
cordialement
ps) pardon pour les fautes
03/10/2006, 07h51
Emmanuel Delahaye

Citation:

Envoyé par zhao

voila j'ai un probleme de programmation mais je ne sais pas comment faire je suis neophite en la matiere voila mon probleme .
<snip 0 lignes de code>

Tu as oublié de poster le code avec lequel tu as un problème, et de préciser quel est le problème.
03/10/2006, 08h37
zhao

Bonjour

heu desolé mais justement je n'ai rien oublier , le fichier dont je parle est generer par une application completement independante .
et je doit faire le programme cité plus haut qui lui aussi est independant .
mais je ne sais ABSOLUMENT pas comment faie ;-(
cordialement
03/10/2006, 08h45
Vigneau

Pourquoi pas un arbre type patricia?

tu cree un arbre, tu le peuple avec les sequences de ton fichier, puis tu le parcours au fur et a mesure de la generation des sequences exhaustives.
Je pencherais pour la recursivité pour la generation, ce qui permet d'arreter la generation des qu'un prefixe n'est pas connu dans l'arbre.
Il existe peut etre plus efficace!
03/10/2006, 10h19
zooro

Bonjour,

Trouves déjà un algo général qui te permettra de résoudre le problème.
Du genre:
- générer et stocker toutes les combinaisons possibles...
- ouvrir le fichier
- pour chaque ligne lue dans le fichier, faire...
- fermer le fichier

Ensuite, tu pourras affiner l'algo en fonction de la solution que tu veux implémenter (tableau(x), arbre, listes, etc.).

On ne fera pas l'exercice à ta place, mais on t'aidera si tu postes ton travail au fur et à mesure en posant des questions sur les problèmes que tu rencontres, ou pour avoir des conseils sur les algos que tu a trouvés, ou sur ton code.

voila ce que je sais faire OH cela n'est pas tres tres joli mais bon ..., mais ensuite je ne sais pas faire :-)
bref je sais generer les combinaisons mais cela s'arrete la et encore je suis quasiment sur qu'il y en a qui ont des algorythme plus performant que ma methode ultra classique ;-)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
 
#include<stdio.h>
#include <dos.h>
#include <time.h>
 
 main()
 
			{
 
	                int tc[10];
	                int nt=0;
			register int i,j,k,l,m,n,o,p,q,r;
 
			FILE *fichier; 
 
			fichier=fopen("test.txt","r"); 
 
                        printf("entrez votre valeur   ");
			scanf("%d",&nt);
			a=nt-9;
 
				  for(i=1;i<=a;i++)
				  for(j=i+1;j<=a+1;j++)
				  for(k=j+1;k<=a+2;k++)
				  for(l=k+1;l<=a+3;l++)
				  for(m=l+1;m<=a+4;m++)
				  for(n=m+1;n<=a+5;n++)
                                  for(o=n+1;o<=a+6;o++)
				  for(p=o+1;p<=a+7;p++)
				  for(q=p+1;q<=a+8;q++)
				  for(r=q+1;r<=a+9;r++)
 tc[0]=i;tc[1]=j;tc[2]=k;tc[3]=l;tc[4]=m;tc[5]=n,
 tc[6]=o;tc[7]=p;tc[8]=q;tc[9]=r;		   
}

:tagcode:

03/10/2006, 11h50
zooro

Utilises les balises CODE (icône # de la barre d'outil) pour encadrer ton code. Ca facilite sa lecture...

Sinon, pour le code, j'avoue être perplexe !
A quoi celà sert-il d'inclure time.h ? Pourquoi ouvrir test.txt en lecture seule ? A quoi sert la valeur saisie ? Quel est l'objectif des boucles imbriquées ?
Bref quelques commentaires dans le code n'auraient pas été inutiles ;)
03/10/2006, 11h59
zhao

desolé pour les balises mais j'ai pas vu .
time.h c'est pour plus tard pour calculer le temps que le programme met .

test.txt c'est le fichier contenant les données que je veux verifier donc je pensais que l'ouverture en lecture suffisait car ce fichier ne seras pas modifier .

la valeur saisie c'est uniquement pour saisir un chiffre compris entre 10 et 25 .

les boucles imbriquées c'est pour generer les combinaisons sinon comment les generer ?

cordialement
03/10/2006, 12h12
zooro

Citation:

Envoyé par zhao

test.txt c'est le fichier contenant les données que je veux verifier donc je pensais que l'ouverture en lecture suffisait car ce fichier ne seras pas modifier .

Ok. Mais chaque chose en son temps.

Citation:

Envoyé par zhao

la valeur saisie c'est uniquement pour saisir un chiffre compris entre 10 et 25 .

Ce n'est pas ce que le code fait. Il permet la saisie d'un entier. Si je saisis 3 ou 2543, ça passe.

Citation:

Envoyé par zhao

les boucles imbriquées c'est pour generer les combinaisons sinon comment les generer ?

Ben là, tu génères 10 nombres compris entre 1 et nt. Si tu veux les conserver, il faut les stocker quelque part. Parce que ton code les écrase à chaque nouveau tour de boucle.

Il y a d'autres problèmes dans le code (pas de test de fopen() par exemple), mais on verra plus tard.

Tu as trouvé un algo permettant de résoudre le problème ? Pas en C, juste en français. C'est très important parce que l'algo te permettra de découper ton programme C en plusieurs fonctions qui seront plus faciles à écrire.
03/10/2006, 12h20
zhao

je ne cherche pas a tester pour le moment le chiffre entré , je part du principe qu'il est bon ,plus tard je m'occuperais de ce probleme ;-)

ensuite que les données enregistrer dans mon tableau TC soit ecraser apres chaque generation de combis c'est voula car une fois tester la combinaisons en cours celle ci ne me sert plus a rien donc je passe a la suivante .
03/10/2006, 14h06
Vigneau

traitement des erreurs

Ce n'est pas forcement un bon calcul de reporter le traitement d'erreur a plus tard: 2 avantages
1/ ca te force a penser aux erreurs donc a valider ce que tu as ecris
2/ le temps que tu a l'impression de perdre en codant le traitement d'erreur tu le gagneras largement au moment de debugger

Apres tu fais comme tu veux!

Citation:

Envoyé par zhao

je ne cherche pas a tester pour le moment le chiffre entré , je part du principe qu'il est bon ,plus tard je m'occuperais de ce probleme ;-)

ensuite que les données enregistrer dans mon tableau TC soit ecraser apres chaque generation de combis c'est voula car une fois tester la combinaisons en cours celle ci ne me sert plus a rien donc je passe a la suivante .

Alors, ton algo, c'est :
Code:

1 2 3 4 5 6 7 8 9 - pour chaque combinaison générée c - ouvrir le fichier f - pour chaque ligne d du fichier f - si (c = d) alors incrémenter compteur - fin pour - fermer le fichier f - fin pour - afficher compteur
C'est ça ?

A priori, il y aura moins de combinaisons dans le fichier que de combinaisons générées, non ? Donc il faudrait plutôt inverser les deux boucles.
Dans tous les cas, il faut s'arranger pour minimiser les opérations sur les fichiers, qui sont coûteuses en temps.
L'algo n'est pas terrible parce qu'il génère toutes les combinaisons possibles à chaque ligne lue dans le fichier. C'est dommage, il vaut mieux les générer une seule fois et les stocker dans un tableau (ou toute autre structure appropriée).

L'algo devriendrait donc :
Code:

1 2 3 4 5 6 7 8 9 10 - générer et stocker toutes les combinaisons possibles - ouvrir le fichier f - pour chaque ligne d de f - pour chaque combinaison générée c - si (c = d) alors incrémenter compteur - fin pour - fin pour - fermer le fichier f - afficher compteur

03/10/2006, 14h34
zooro

Citation:

Envoyé par Vigneau

Ce n'est pas forcement un bon calcul de reporter le traitement d'erreur a plus tard: 2 avantages
1/ ca te force a penser aux erreurs donc a valider ce que tu as ecris
2/ le temps que tu a l'impression de perdre en codant le traitement d'erreur tu le gagneras largement au moment de debugger
Apres tu fais comme tu veux!

+1

Mais de toute façon, il faut d'abord avoir une idée du programme avant de se mettre à coder.
03/10/2006, 19h29
siplusplus

Bonjour,
Je pense que le plus simple est de créer un générateur de combinatoire
et de mettre chaque résultat dans une base de donnée.
Ainsi il n'y aura plus besoin de refaire une génération de combinaison pour
chaque ligne de ton fichier.
Il suffirat alors d'extraire ligne par ligne les données du fichier
et ensuite de faire une requête sql pour la combinaison correspondante.

Il y a aussi une méthode matricielle mais est trop longue à expliquer et
n'est intéressante que pour une analyse poussée en fonction de l'énoncé.

:)
03/10/2006, 19h40
zooro

Citation:

Envoyé par siplusplus

Je pense que le plus simple est de créer un générateur de combinatoire et de mettre chaque résultat dans une base de donnée.

Ma foi, on arrivera sûrement aussi à placer un réseau de neurones et quelques algos génétiques quelque part en serrant bien.

Peut-être que le char Leclerc n'est pas l'outil le plus adapté pour écraser la mouche...;)
...encore que, ça dépend de la taille de la mouche... :mouarf:
03/10/2006, 19h51
Gnux

Bonjour
Moi j'ai une question au sujet de ce problème: te donnes ton le fichier avec toutes les combinatoires des nombres 1 à 25 par paire de 10 ou bien est ce à toi de le générer d'abord pour ensuite appliquer par exemple l'algo de zooro?
03/10/2006, 20h12
Gnux

Citation:

Envoyé par zhao

les boucles imbriquées c'est pour generer les combinaisons sinon comment les generer ?

Pour la génération de combinaisons certaines pistes avaient été abordées dans ce sujet: http://www.developpez.net/forums/sho...ht=combinaison
04/10/2006, 01h29
zhao

Bonjour a tous :lol:

escusez pour la reponse tardive mais vu le decalage horaire ;-)
donc je vais repondre aux interogations :

Vigneau a écrit :
Ce n'est pas forcement un bon calcul de reporter le traitement d'erreur a plus tard: 2 avantages

ok avec toi mais je me sens capable de gerer ce genre de chose c'est pour cela que je n'insiste pas sur ce point .

***************************************

zooro a ecrit

Alors, ton algo, c'est :
Code :

- pour chaque combinaison générée c - ouvrir le fichier f - pour chaque ligne d du fichier f - si (c = d) alors incrémenter compteur - fin pour - fermer le fichier f - fin pour - afficher compteur

MON ALGO c'est :

ouviri le fichier en lecture tant que combi a generer
pour chaque combinaisons generer
lire chaque chiffre de chaque ligne de mon fichier jusqu'a la fin du fichier
verifier si chaque chiffre de la combinaisons generer a des chiffres en commun avec les chiffres des lignes de mon fichier
si oui
incrementer compteur
quand tous les chiffres de la combinaisons en cours a ete comparer avec tous les chiffres de chaque ligne de mon fichier .
revenir au debut du fichier
generer combinaisons suivante et refaire operation
quand toute les combinaisons on ete generer
fermer le fichier
afficher le resultat
fin du programme
*******************************************************
zooro a ecrit :
A priori, il y aura moins de combinaisons dans le fichier que de combinaisons générées, non ? Donc il faudrait plutôt inverser les deux boucles.
Dans tous les cas, il faut s'arranger pour minimiser les opérations sur les fichiers, qui sont coûteuses en temps.
L'algo n'est pas terrible parce qu'il génère toutes les combinaisons possibles à chaque ligne lue dans le fichier. C'est dommage, il vaut mieux les générer une seule fois et les stocker dans un tableau (ou toute autre structure appropriée).

OUI il y auras moins de combi dans le fichier que de combinaisons generer

generer chaque combi je ne pense pas que cela prenne beaucoup de temps mais j'y ais pensé rassure toi ,mais cela me gene un peu de stocker toutes ses combinaisons dans un tableau a 2 dimension car C ( 10 25 ) cela represente tout de meme 3 268 760 combinaisons donc cela represente quand meme un sacre tableau mais sinon je suis tout a fait ok avec toi ;-)

************************************
Gnux Bonjour
Moi j'ai une question au sujet de ce problème: te donnes ton le fichier avec toutes les combinatoires des nombres 1 à 25 par paire de 10 ou bien est ce à toi de le générer d'abord pour ensuite appliquer par exemple l'algo de zooro?

pourquoi par paire de 10 ? c'est moi qui genere les combinaisons .

****************************************************

siplusplus Bonjour,
Je pense que le plus simple est de créer un générateur de combinatoire
et de mettre chaque résultat dans une base de donnée.
Ainsi il n'y aura plus besoin de refaire une génération de combinaison pour
chaque ligne de ton fichier.
Il suffirat alors d'extraire ligne par ligne les données du fichier
et ensuite de faire une requête sql pour la combinaison correspondante.

un generateur de combinatoire c'est quoi ?
mettre les resultats dans une base de données extraire ligne par ligne executer une requete etc... cela va a mon avis mettre trop de temps .

****************************************************

merci a tous
04/10/2006, 10h15
siplusplus

Citation:

Envoyé par zooro

Peut-être que le char Leclerc n'est pas l'outil le plus adapté pour écraser la mouche...;)
...encore que, ça dépend de la taille de la mouche... :mouarf:

Ces chars ne sont pas capable de faire mouche? :mouarf:

Bon sérieusement,

Citation:

Envoyé par zhao

un generateur de combinatoire c'est quoi ?

Est-ce que ce qui suit répondra à ta question?

Citation:

Envoyé par zhao

MON ALGO c'est :

ouviri le fichier en lecture tant que combi a generer
pour chaque combinaisons generer
lire chaque chiffre de chaque ligne de mon fichier jusqu'a la fin du fichier
verifier si chaque chiffre de la combinaisons generer a des chiffres en commun avec les chiffres des lignes de mon fichier
si oui
incrementer compteur
quand tous les chiffres de la combinaisons en cours a ete comparer avec tous les chiffres de chaque ligne de mon fichier .
revenir au debut du fichier
generer combinaisons suivante et refaire operation
quand toute les combinaisons on ete generer
fermer le fichier
afficher le resultat
fin du programme
*******************************************************
zooro a ecrit :
A priori, il y aura ...., qui sont coûteuses en temps.
L'algo n'est pas terrible parce qu'il génère toutes les combinaisons possibles à chaque ligne lue dans le fichier...

OUI il y auras moins de combi dans le fichier que de combinaisons generer

J'aurais peut-être dû mettre "générateur de combinaison" mais j'ignore si ce sont des permutations, arrangements avec ou sans répétitions, l'intervalle exacte ...

Citation:

Envoyé par zooro

C'est dommage, il vaut mieux les générer une seule fois et les stocker dans un tableau (ou toute autre structure appropriée).

Citation:

Envoyé par zhao

mettre les resultats dans une base de données extraire ligne par ligne executer une requete etc... cela va a mon avis mettre trop de temps .

Je suis d'accord avec zooro pour ce qui est de stocker une seule fois toutes les combinaisons.
Quand au stockage en lui même, que ce soit en mémoire, dans un fichier, un SGBD ou autre cela améliore grandement le traîtement car il ne reste plus qu'une comparaison entre deux combinaisons et ton algorithme est séparé en 2.
Le premier génère les combinaisons et les mémorises.
Le second compare ce qui est mémorisé avec le fichier, incrémente le compteur et affiche le résultat.
Au final, cela te donneras 2 programmes indépendants.
Et cela fera gagner plus de temps que de devoir parcourir des milliers de fois des boucles imbriquées.

Sauf erreur de ma part, tu ne peux pas te déplacer comme tu veux dans un fichier texte. Il faut le fermer et le réouvrir pour revenir au début.

Bon, algo simple et (relativement optimisé):
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 - ouvrir le fichier - pour chaque ligne lue - stocker la combinaison dans le tableau t - fin pour - fermer le fichier - pour chaque combinaison possible - générer la combinaison c - comparer la combinaison c à chacune des combinaisons du tableau t - si les deux sont égales, incrémenter le compteur - fin pour - afficher le compteur
Comme ça, tu ne génères les combinaisons possibles qu'une seule fois et sans les stocker. Et tu ne lis le fichier qu'une seule fois aussi.

hein ?

y a quelque chose que je piges pas tu dis :
Citation:
MON ALGO c'est :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 ouviri le fichier en lecture tant que combi a generer pour chaque combinaisons generer lire chaque chiffre de chaque ligne de mon fichier jusqu'a la fin du fichier verifier si chaque chiffre de la combinaisons generer a des chiffres en commun avec les chiffres des lignes de mon fichier si oui incrementer compteur quand tous les chiffres de la combinaisons en cours a ete comparer avec tous les chiffres de chaque ligne de mon fichier . revenir au debut du fichier generer combinaisons suivante et refaire operation quand toute les combinaisons on ete generer fermer le fichier afficher le resultat fin du programme
ça veut dire quoi exactement ça ? :

Citation:

verifier si chaque chiffre de la combinaisons generer a des chiffres en commun avec les chiffres des lignes de mon fichier

si j'ai bien compris ça, tu veux vérifier si les chiffres compris dans ta combinaison apparaissent dans ton fichier, et incrémenter un compteur si c'est le cas.

Maintenant mes questions sont les suivantes :

souhaites tu incrémenter ton compteur :
- une fois si tous les nombres de ta combinaisons apparaissent au moins une fois dans le fichier
- une fois si tous les nombres de ta combinaisons apparaissent tous sur une même ligne de ton fichier
- une fois si un des nombres de ta combinaison apparait dans ton fichier
- une fois si une ligne de ton fichier est strictement égale à ta combinaison
- à chaqe fois qu'une ligne de ton fichier est strictement égale à ta combinaison
- à chaque fois que tous les nombres de ta combinaison apparaisent sur une même ligne de ton fichier
- à chaque fois qu'un nombre de ta combinaison apparait dans le fichier

Si c'est le dernier cas qui t'interesse tu n'a qu'à faire un tableau T[25] avec T[i] pour 0<=i<=24 T[i]={nbre d'occurence de i dans le fichier} et comme ça tu n'a qu'à augmenter ton compteur comme ça pour ta combinaison C=c1,c2,...,c10 et cpt = cpt + T[c1]+T[c2]+...+T[c10] et ce pour chaque combinaison

Mais à mon avis c'est pas du tout ça qui t'interesse et je dois être à côté de la plaque.