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 ?