Heim > Backend-Entwicklung > C++ > Wie implementiert man ein kartesisches Produkt von Vektoren mithilfe von Rekursion und Iteration?

Wie implementiert man ein kartesisches Produkt von Vektoren mithilfe von Rekursion und Iteration?

Patricia Arquette
Freigeben: 2024-12-08 17:11:12
Original
360 Leute haben es durchsucht

How to Implement a Cartesian Product of Vectors Using Recursion and Iteration?

Implementieren eines kartesischen Vektorprodukts mit Rekursion und Iteration

Sie haben einen Vektor aus Vektorelementen unterschiedlicher Größe und möchten ein kartesisches Produkt generieren Produkt ihrer Elemente.

Zunächst kann ein rekursiver Ansatz verwendet werden:

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

// Recursive Cartesian product function

void cart_product(

    Vvi& rvvi,  // Result vector of vectors

    Vi& rvi,   // Current vector

    Vvi::const_iterator me, // Current vector in input

    Vvi::const_iterator end) // Input vector end

{

    if (me == end) {

        // Push the current result to the final result

        rvvi.push_back(rvi);

        return;

    }

     

    // Iterate through the current vector

    const Vi& mevi = *me;

    for (Vi::const_iterator it = mevi.begin(); it != mevi.end(); it++) {

        // Add current element to result

        rvi.push_back(*it);

         

        // Recurse to add subsequent elements

        cart_product(rvvi, rvi, me + 1, end);

         

        // Remove added element for further recursion

        rvi.pop_back();

    }

}

Nach dem Login kopieren

Betrachten Sie nun den iterativen Ansatz:

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

// Iterative Cartesian product function

void cart_product(

    Vvi& out,  // Result vector of vectors

    Vvi& in)  // Input vector of vectors

{

    Vd vd; // Vector of iterator structs

    // Initialize iterators to start of vectors

    for (Vvi::const_iterator it = in.begin(); it != in.end(); ++it) {

        Digits d = {(*it).begin(), (*it).end(), (*it).begin()};

        vd.push_back(d);

    }

     

    // Iterative loop to generate product vectors

    while (1) {

        // Create result vector from iterated elements

        Vi result;

        for (Vd::const_iterator it = vd.begin(); it != vd.end(); it++) {

            result.push_back(*(it->me));

        }

        out.push_back(result);

         

        // Increment iterator

        // Reset iterator at end, increment neighboring iterator

        for (Vd::iterator it = vd.begin(); ; ) {

            ++(it->me);

            if (it->me == it->end) {

                if (it + 1 == vd.end()) {

                    // End of product

                    return;

                } else {

                    // Cascade reset

                    it->me = it->begin;

                    ++it;

                }

            } else {

                // Break from loop

                break;

            }

        }

    }

}

Nach dem Login kopieren

Das obige ist der detaillierte Inhalt vonWie implementiert man ein kartesisches Produkt von Vektoren mithilfe von Rekursion und Iteration?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Quelle:php.cn
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Neueste Artikel des Autors
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage