C++

Forum

 
 
Variable nested loops for variable vector sizes to find the element combinations

AkshayMalige (20)
Hello,

I am trying to get the combination of my vector element from N number of vectors of variable size. Is it possible to do it by recursion? i am not able to find a suitable solution even though there are a few online.

I am currently using multiple for loops and this works only if i know the number of vectors i have.

For example in this case its N =4.

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
 
#include <iostream>
#include <vector>
using namespace std;
int main()
{
    std::vector<int> vec1 ={1,2,3,4};
    std::vector<int> vec2 ={1,2,3};
    std::vector<int> vec3 ={1,2,3,4,5};
    std::vector<int> vec4 ={1,2};
    
    for (int a=0; a<vec1.size(); a++)
    {
        for (int b=0; b<vec2.size(); b++)
        {
            for (int c=0; c<vec3.size(); c++)
            {
                for (int d =0; d<vec4.size(); d++)
                {
                    printf("%i,  %i,  %i,  %i\n",vec1[a],vec2[b],vec3[c],vec4[d]);
                }
   
            }
        }
    }

    return 0;
}
Last edited on
JLBorges (13770)
This is one way:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
#include <iostream>
#include <vector>
#include <string>

void print_tuples( const std::vector< std::vector<int> >& vectors,
                   std::size_t pos = 0, std::string prefix = {} )
{
    if( pos == vectors.size() ) std::cout << prefix << '\n' ;
    else
    {
        for( int v : vectors[pos] ) // note: this assumes that the vector is not empty
            print_tuples( vectors, pos+1, prefix + std::to_string(v) + ' ' ) ;
    }
}

int main()
{
    print_tuples( { {1,2,3}, {1,2,3}, {1,2,3,4,5}, {1,2}, {1,2,3} } ) ;
}
AkshayMalige (20)
Thank you very much for your time and interest JLBorges,

The example i had given above is just an attempt to explain the problem, but the actual problem seems to a bit different than that.

Is there any other way where i can do this for cases where i dont know the elements of the vector since it depends on my data file.

Is there a way to do this such that i can do some operations on the output (i.e the combination) by putting the in one more vector ? I am not sure if what you suggested can modified in such a way since i am not an expert.
Last edited on
JLBorges (13770)
> Is there a way to do this such that i can do some operations on the output
> (i.e the combination) by putting the in one more vector ?

Something like this, perhaps:

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
 
#include <iostream>
#include <vector>
#include <cassert>

void add_tuples( const std::vector< std::vector<int> >& vectors, std::size_t pos,
                 std::vector<int> prefix, std::vector< std::vector<int> >& result )
{
    if( pos == vectors.size() ) result.push_back(prefix) ;
    else if( vectors[pos].empty() ) add_tuples( vectors, pos+1, prefix, result ) ; // note: skip empty vectors
    else
    {
        for( int v : vectors[pos] )
        {
            prefix.push_back(v) ;
            add_tuples( vectors, pos+1, prefix, result ) ;
            prefix.pop_back() ;
        }
    }
}

std::vector< std::vector<int> > make_tuples( const std::vector< std::vector<int> >& vectors )
{
    std::vector< std::vector<int> > result ;
    add_tuples( vectors, 0, {}, result ) ;
    return result ;
}

int main()
{
    const std::vector< std::vector<int> > vectors =  { {1,2,3}, {1,2,3}, {}, {1,2,3,4,5}, {}, {1,2}, {1,2,3} } ;

    const auto tuples = make_tuples(vectors) ;

    std::size_t ntups = 0 ;
    for( const auto& tup : tuples )
    {
        std::cout << ++ntups << ". [ " ;
        for( int v : tup ) std::cout << v << ' ' ;
        std::cout << "]\n" ;
    }

    /////////////////////////////////////////////////////////////////////////////////
    ////////////////////////// sanity checks ////////////////////////////////////////
    /////////////////////////////////////////////////////////////////////////////////
    
    std::size_t num_empty_vecs = 0 ;
    std::size_t expected_ntups = 1 ;
    for( const auto& vec : vectors )
    {
        if( !vec.empty() ) expected_ntups *= vec.size() ;
        else ++num_empty_vecs ;
    }

    assert( num_empty_vecs < vectors.size() && ntups == expected_ntups ) ;

    std::cout << "\n------------\n\n"
              << "#vectors: " << vectors.size() << '\n'
              << "  #empty: " << num_empty_vecs << '\n'
              << "tup size: " << vectors.size() - num_empty_vecs << '\n'
              << " #tuples: " << ntups << '\n' ;
}

http://coliru.stacked-crooked.com/a/1868740b317d30a5
https://rextester.com/HXM65936
AkshayMalige (20)
Thank you very much JLBorges, this works for me but I get stuck with this method in my the next stage for some reson.

i.e, is there a way to now get the combination of vectors by giving vector of vector as an input.

ex. for a case of 4 vectors

1
2
3
4
 
    std::vector<std::vector<int>> vec1 = {{1,2},{3,4}};
    std::vector<std::vector<int>> vec2 = {{5,6},{7,8}};
    std::vector<std::vector<int>> vec3 = {{9,10}};
    std::vector<std::vector<int>> vec4 = {{11,12},{13,14}};


I need an out put vector combinations as follows
1
2
3
4
5
6
7
8
9
 
1. {{1,2},{5,6},{9,10},{11,12}}

2. {{1,2},{5,6},{9,10},{13,14}}

3. {{1,2},{7,8},{9,10},{11,12}}

4. {{1,2},{7,8},{9,10},{13,14}}
    
ans so on .....

Last edited on
AkshayMalige (20)
But, Seems like i figured out .


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
 
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
void add_tuples( const std::vector< std::vector<std::vector<int> > >& vectors, std::size_t pos,
                 std::vector<std::vector<int>> prefix, std::vector< std::vector<std::vector<int> > >& result )
{
    if( pos == vectors.size() ) result.push_back(prefix) ;
    else if( vectors[pos].empty() ) add_tuples( vectors, pos+1, prefix, result ) ; // note: skip empty vectors
    else
    {
        for( std::vector<int> v : vectors[pos] )
        {
            prefix.push_back(v) ;
            add_tuples( vectors, pos+1, prefix, result ) ;
            prefix.pop_back() ;
        }
    }
}

std::vector< std::vector<std::vector<int> > > make_tuples( const std::vector< std::vector<std::vector<int> > >& vectors )
{
    std::vector< std::vector<std::vector<int> > >result ;
    add_tuples( vectors, 0, {}, result ) ;
    return result ;
}

int main()
{
    std::vector<std::vector<int>> vec1 = {{1,2},{3,4}};
    std::vector<std::vector<int>> vec2 = {{5,6},{7,8}};
    std::vector<std::vector<int>> vec3 = {{9,10}};
    std::vector<std::vector<int>> vec4 = {{11,12},{13,14}};
    std::vector<std::vector<std::vector<int>>> vec;
    vec.push_back(vec1);
    vec.push_back(vec2);
    vec.push_back(vec3);
    vec.push_back(vec4);
    const std::vector< std::vector<std::vector<int> > >vectors =  vec ;

    const auto tuples = make_tuples(vectors) ;

    std::size_t ntups = 0 ;
    for( const auto& tup : tuples )
    {
        std::cout"\n{";
        for (int a =0; a<tup.size(); a++)
        {
            for (int b=0; b<tup[a].size(); b++)
            {
                std::cout<<tup.at(a).at(b)<<" ";

            }
        }
        std::cout << "}\n" ;
    }

}

Last edited on
Topic archived. No new replies allowed.