Discussion :

[libredr]

Bonjour,

J'ai un probleme conceptuel et je recherche de l'aide.

J'ai un vecteur qui contient egalement un certain nombre variable de vecteurs de double:
std::vector<std::vector<double> > vecteur

J'aimerais etre capable d'extraire le produit cartesien de ce vecteur, en prenant toutes les combinaisons possibles.

Par exemple, si mon vecteur contient:

< <1 , 2, 3>, <4, 5>, <6, 7> >

J'aimerais construire les combinaisons:
<1,4,6><1,4,7>,<1,5,6><1,5,7> ... <3,5,7>

Comment faire? Comme mon nombre de vector<double> est lui-meme variable, je ne peux pas utiliser un nombre fixe de boucles for. Si jamais mon vecteur devient:
< <1 , 2, 3>, <4, 5>, <6, 7>, <8> >

la meme fonction devrait m'extraire:
<1,4,6,8>,<1,4,7,8> etc...


J'ai pense creer un tableau d'iterateurs, mais est-ce la meilleure methode? Utiliser la recursivite peut-etre ?


Merci d'avance.

[rikau2]

Salut,

Est-ce que tu as commencé à implementer?

Comment stocks tu tes donnes?

[libredr]

Salut,

Est-ce que tu as commencé à implementer?

Comment stocks tu tes donnes?

Oui, en fait j'utilise la STL et des structures. Pour etre tout a fait exact:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
struct parameterRange {
string name;
vector<double> values;
};
 
vector<parameterRange> ranges;

Donc j'ai stocke mes ranges sous cette forme (si j'utilise < pour representer un vecteur, et {} pour delimiter ma structure parameterRange):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
Pseudocode:
 
<{"A",<1,2,3>},{"B",<4,5>}>

Ce que je veux faire est:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
struct nvpair {
string name;
double value;
};
 
Pseudocode ou {} represente une structure nvpair:
< <{"A",1},{"B",4}>,<{"A",1},{"B",5}>,...,<{"A",3},{"B",5}>>

mais sachant que mon vecteur ranges peut contenir un nombre variable de structures parameterRange.

[Jack_serious]

Avec la recursivite tu dois pouvoir t'en sortir sans trop de problemes.

Il ne faut juste pas que tu ai trop de vectors a parcourir sinon ta stack risque de peter une durite .

Un morceau de code tres vite fait qui fait un produit cartesien:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
#include <vector>
#include <cstdlib>
#include <iostream>
 
void    get_cart_prod(std::vector<std::vector<double> >::iterator end,
        std::vector<std::vector<double> > *cart_prod,
        std::vector<std::vector<double> >::iterator tabs_it,
        std::vector<double> *cart_prod_unit)
{
    std::vector<double>::iterator   tab_it = tabs_it->begin();
    std::vector<double>::iterator   tab_end = tabs_it->end();
 
    while (tab_it != tab_end)
    {
        std::vector<double> *new_cart_unit = new std::vector<double>(*cart_prod_unit);
        new_cart_unit->push_back(*tab_it);
 
        if (tabs_it + 1 != end)
            get_cart_prod(end, cart_prod, tabs_it + 1, new_cart_unit);
        else
            cart_prod->push_back(*new_cart_unit);
        ++tab_it;
    }
    return ;
}
 
int		main(void)
{
    std::vector<std::vector<double> >   tabs(2);
 
    tabs[0] = std::vector<double>(3);
    tabs[0][0] = 2;
    tabs[0][1] = 3;
    tabs[0][2] = 4;
 
    tabs[1] = std::vector<double>(2);
    tabs[1][0] = 1;
    tabs[1][1] = 5;
 
    std::vector<std::vector<double> >   cart_prod;
    std::vector<std::vector<double> >::iterator tabs_it;
 
    tabs_it = tabs.begin();
 
    std::cout << "Will fill cartesian prod table" << std::endl;
    get_cart_prod(tabs.end(), &cart_prod, tabs_it, new std::vector<double>());
 
    std::cout << "Will print cart table" << std::endl;
    tabs_it = cart_prod.begin();
 
    while (tabs_it != cart_prod.end())
    {
        std::vector<double>::iterator it;
        std::vector<double>::iterator end;
 
	it = tabs_it->begin();
	end = tabs_it->end();
        while (it != end)
        {
            std::cout << *it << ' ';
            ++it;
        }
        std::cout << std::endl;
        ++tabs_it;
    }
 
    return (EXIT_SUCCESS);
}

C'est fait rapidement donc desole pour la proprete.
Je n'ai rien supprime de ce que j'ai cree pour eviter d'alourdir le code .
Mais ca devrait te donner une idee de la structure de la fonction recursive...

Ca donne la sortie suivante:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
Will fill cartesian prod table
Will print cart table
2 1 
2 5 
3 1 
3 5 
4 1 
4 5

Bonne soiree

[libredr]

Ouaouh ca a l'air vraiment pas mal!
Je vais m'adapter ca mais ca me semble vraiment cool. Merci beaucoup je vais travailler avec ca

[libredr]

En effet la recursivite va limiter la taille des tableaux. Y-a-t-il une methode iterative ?

[Jack_serious]

Surement.

Tout ce qui se fait en recursif peut se faire en iteratif.

En precalculant la taille du vector resultat et de ses vectors membres.
Ca se fait en deux boucles.

Apres tu dois avoir une autre grosse boucle en fonction des resultats trouves avant pour remplir les vector resultats.

Un papier, un crayon et tu devrais pouvoir trouver ca sans trop de probleme

Si j'ai un peu de temps dans la soiree je verrais si je peux pondre un autre morceau de code qui fait ca mais je ne te promet rien.

Bonne continuation

[libredr]

Surement.

Tout ce qui se fait en recursif peut se faire en iteratif.

En precalculant la taille du vector resultat et de ses vectors membres.
Ca se fait en deux boucles.

Ah OK, je me doutais qu'il fallait faire ca. N'hesite pas a poster ta solution quand meme
En tout cas merci beaucoup