Produit cartesien sur un nombre variable de vecteurs

Version imprimable

08/01/2008, 15h29
libredr

Produit cartesien sur un nombre variable de vecteurs

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.
08/01/2008, 16h17
rikau2

Salut,

Est-ce que tu as commencé à implementer?

Comment stocks tu tes donnes?
08/01/2008, 17h45
libredr
Citation:

Envoyé par rikau2

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:

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:

1 2 3 4 Pseudocode: <{"A",<1,2,3>},{"B",<4,5>}>
Ce que je veux faire est:
Code:

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.

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 :D.

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

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
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 :aie:.
Mais ca devrait te donner une idee de la structure de la fonction recursive...

Ca donne la sortie suivante:

Code:

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 :)

08/01/2008, 18h21
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 :D
08/01/2008, 18h39
libredr

En effet la recursivite va limiter la taille des tableaux. Y-a-t-il une methode iterative ?
08/01/2008, 18h54
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 :D

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 :)
08/01/2008, 19h43
libredr

Citation:

Envoyé par 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.

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