I implemented an O(N^2) algorithmic solution but not sure it is better than my previous implementation Find Triangle Triplets from a list of given numbers in case of performance. I adapted almost all suggestions from answer except a structure to keep the triangle triplets.The reasons to ignore the suggestion are follows:
This program added additional feature to remove duplicates from the output
To achieve this additional feature in better way is to keep the data structure as vector instead of suggested data structure 'structure' in place of vector.
- Moreover there is no additional advantage, instead a change in the coding style with this suggested change in my perspective
And @nhgrif pointed out in chat my previous solution spitting duplicate triplets and that flaw is taken care here. Let me know is there any other option to make my code better.
#include<vector>
#include<iostream>
#include<algorithm>
#include<set>
bool isTriangleTriplet(const int a, const int b, const int c)
{
if( ( a + b ) > c && ( a + c ) > b && ( b + c ) > a)
{
return true;
}
return false;
}
std::vector<std::vector<int>> findTriangleTriplets( const std::vector<int>& vec_input )
{
auto size = vec_input.size();
std::vector<std::vector<int>> triplets;
for( unsigned int i = 0; i < size; ++i )
{
for( unsigned int j = i+1; j < size; ++j )
{
std::vector<int> temp;
temp.emplace_back( vec_input.at( i ) );
temp.emplace_back( vec_input.at( j ) );
triplets.emplace_back( temp );
} }
std::vector<std::vector<int>> temp_triplets;
for(auto &pair : triplets)
{
std::vector<int> pers_vec( pair );
bool flag = false;
for( auto &num : vec_input )
{
if( isTriangleTriplet( pair.at( 0 ), pair.at( 1 ) , num) )
{
if( flag )
{
std::vector<int> temp( pers_vec );
temp.emplace_back( num );
temp_triplets.push_back( temp );
}
else if( std::count( std::begin( pair ), std::end( pair ), num ) < 2 )
{
pair.emplace_back( num );
flag=true;
}
}
}
}
for( auto & x: temp_triplets )
{
triplets.emplace_back( x );
}
return triplets;
}
std::set<std::vector<int>> SieveDuplicates( std::vector<std::vector<int>> & triplets )
{
std::set<std::vector<int>> sieved_triplets;
for( auto &x : triplets )
{
std::sort( std::begin( x ), std::end( x ) );
sieved_triplets.emplace( x );
}
return sieved_triplets;
}
int main()
{
const std::vector<int> vec_input { 2, 3, 4, 1, 5, 6};
std::vector<std::vector<int>> triplets = findTriangleTriplets( vec_input );
std::cout<< "Triplet size:" << triplets.size()<<"\n";
for ( auto &x : triplets)
{
for( auto &y : x )
{
std::cout<<y<<" ";
}
std::cout<<"\n";
}
std::set<std::vector<int>> sieved_triplets=SieveDuplicates( triplets );
std::cout<< "Sieved Triplet size:" << sieved_triplets.size()<<"\n";
for ( auto &x : sieved_triplets )
{
for( auto &y : x )
{
std::cout<<y<<" ";
}
std::cout<<"\n";
}
}