3 combinations

[donvigor]

so i implemented this short code to do a 3 combination of any number of numbers given, but i think it does not work properly, can anyone suggest something better? thanks

  
void make_three_sures (std::vector<int> & cross)
{
 /*for(auto p = cross.begin() ; p != cross.end(); p++)
    {
     for(auto pt = cross.begin()++; pt != cross.end() ; pt++)
        {
         head.push_back(combi_t( *p, *pt, *(pt++) ) );
        }
    }*/

for (int p = 0; p < cross.size(); p++)
   {  for(int pt = (p+1); pt < cross.size(); pt++)

      { if (pt>cross.size()) break;;
      head.push_back(combi_t( cross[p], cross[pt], cross[pt++]) );
      }
   }


}

to make clearer what i want to achieve:::

a natural number COMBINATION 3
so if our numbers are 4 and they are ; 0,1,2,3,
then we want to achieve a list of type combi_t with the combi_ts containing
(0,1,2 ) (0,1,3,) (0,2,3) (1,2,3)

[JLBorges]

Brute force:

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

std::set< std::vector<int> > unique_n_combinations( std::vector<int> seq, std::size_t n = 3 )
{
    std::set< std::vector<int> > n_tuples ;
    
    if( seq.size() >= n ) do
    {
        std::vector<int> temp( seq.begin(), seq.begin() + n );
        std::sort( temp.begin(), temp.end() ) ;
        n_tuples.insert( std::move(temp) ) ;
    }
    while( std::next_permutation( seq.begin(), seq.end() ) ) ;

    return n_tuples ;
}

void print_unique_n_combinations( std::vector<int> seq, std::size_t n = 3 )
{
    std::sort( seq.begin(), seq.end() ) ;
    seq.erase( std::unique( seq.begin(), seq.end() ), seq.end() ) ;
    
    for( const auto& n_tuple : unique_n_combinations( seq, n ) )
    {
        for( int v : n_tuple ) std::cout << v << ' ' ;
        std::cout << '\n' ;
    }
    std::cout << "-----------------------------\n" ;
}

int main()
{
    print_unique_n_combinations( { 0, 1, 2, 3 }, 3 ) ;
    print_unique_n_combinations( { 0, 1, 2, 3, 4, 5, 6 }, 4 ) ;
}

http://coliru.stacked-crooked.com/a/70e9db306bff0b53

[donvigor]

thanks sooo much JLBorges!!!
now am going to study this code well..will be back with any questions if i have them

[donvigor]

look Master JLBorges, your level of programming is super top notch!!! you made months of head scratching looks soo easy. thanks soo much!!!

[donvigor]

one more question Sir,
std::set< std::vector> > n_tuple ;

a set which contiains unique vectors ; how do i access indivual values of each vector in the set?

can something of the sort like set.vector_one.first element? set.vector_one.last_element?
something of the sort...

[anup30]

> a set which contiains unique vectors ; how do i access indivual values of each vector in the set?

iterators can be used for that. but when you do operations on all elements, ranged based for loop is easier - as line 26 to 30 of JLB's code. here n_tuple is each (one at a time) element of set, and v is each element of vector.

> something of the sort...

do you mean line 13 ? if you don't sort it, it will print all permutations nPr (take r elements each time from n elements), instead of all combinations nCr.

[JLBorges]

> a set which contiains unique vectors ; how do i access indivual values of each vector in the set?

The code for doing that is already there in print_unique_n_combinations().
This uses a range-based loop http://www.stroustrup.com/C++11FAQ.html#for

std::set< std::vector> > set_of_vectors ;

// ...

for( const auto& vec : set_of_vectors) // for each vector vec in set_of_vectors
{
    for( int v : vec ) std::cout << v << ' ' ; // for each int v in the vector
    std::cout << '\n' ;
}

Also see this tutorial on using vectors: https://www.mochima.com/tutorials/vectors.html


Have you understood the code? Can you explain:
Line 16: What does std::next_permutation() do? When does in return false?
Line 12: What does the vector temp contain
Line 13: Why is it sorted before insertion into the set?

[anup30]

@JLBorges, why do you erase in line 24 seq.erase( std::unique( seq.begin(), seq.end() ), seq.end() ) ;

i think without it, the program will allow repeated values in the vector.
e.g. print_unique_n_combinations( { 4, 1, 2, 3, 4, 4}, 3 ) ;
so, one of the combination will be: 4 4 4
and, 1 2 4 will be printed only once (not 3 times for 3 "different" 4s)

[JLBorges]

Yes.
Without unique values, there is an inherent ambiguity in combinations like:
1 4 4, 2 4 4 (which two fours?) or 1 2 4, 1 3 4 (which four?)

[donvigor]

thanks Sir JLBorges, you're right!
what confused me a lil bit is the fact that the set name is n_tuple and the vector name too is n_tuple...
nice though, so with a double for loop we get the outer shell then the inside.

i got it !