Discrete Find all functions from Set A - > B

[Bdanielz]

Hi all,

I am stuck on this problem and I am at that point where I really could use some help. My task is...

Say we have the set A = {1,2} and set B = {a,b}

This would imply four valid functions using [A]^[B]
e.g

{(1,a)(2,b)}, {(1,b),(2,b)}, {(2,a),(2,b)} {(1,b),(2,a)}

I need to create a "set -> set" function printer.
Any ideas on how you would tackle this?

I am brain dead at this point!!
Please help.

[JLBorges]

#include <iostream>
#include <set>
#include <utility>

template < typename SET_A, typename SET_B >
auto cross_product( const SET_A& a, const SET_B& b )
{
    using value_type_a = typename SET_A::value_type ;
    using value_type_b = typename SET_B::value_type ;
    using value_type_result = std::pair< value_type_a, value_type_b > ;

    std::set<value_type_result> result ;

    for( const auto& first : a ) for( const auto& second : b ) result.emplace( first, second ) ;
    return result ;
}

int main()
{
    std::set<int> a { 1, 2, 3, 4, 5 } ;
    std::set<char> b { 'a', 'b', 'c' } ;

    for( auto pair : cross_product(a,b) ) std::cout << pair.first << pair.second << ' ' ;
    std::cout << '\n' ;
}

http://coliru.stacked-crooked.com/a/283db20608cc8dd0

[Bdanielz]

Sorry if I am not explaining my self.

with this

    std::set<int> a { 1, 2 } ;
    std::set<char> b { 'a', 'b' } ;

my expected output would be *(see link - sorry for any confusion)

{(a,1)(b,2)}, {(a,1),(b,2)}, {(a,2),(b,2)} {(a,2),(b,1)}

Visually what should be happening

http://i.imgur.com/dSg1o4G.png

Any other tips you can offer would be great.
I was able to derive the cross-product on my own what you posted is much nicer, but I am still at loss.

[ne555]

your output does not correspond with the drawing
(a,1), (b,2) is duplicated and (a,1), (b,1) is missing

In your first example {(2,a),(2,b)} does not use the `1' element from the first set.


¿how would generalise for bigger sets?

[JLBorges]

Extreme brute force:

#include <iostream>
#include <set>
#include <utility>
#include <type_traits>
#include <algorithm>
#include <ctime>

template < typename SET_A, typename SET_B >
auto cross_product( const SET_A& a, const SET_B& b )
{
    using value_type_a = typename SET_A::value_type ;
    using value_type_b = typename SET_B::value_type ;
    using value_type_result = std::pair< value_type_a, value_type_b > ;

    std::set<value_type_result> result ;

    for( const auto& first : a ) for( const auto& second : b ) result.emplace( first, second ) ;
    return result ;
}

template < typename SET_A, typename SET_B >
auto cross_cross_product( const SET_A& a, const SET_B& b )
{
    const auto cp = cross_product( a, b ) ;
    return cross_product( cp, cp ) ;
}

template < typename SET_A, typename SET_B >
auto operator_cap( const SET_A& a, const SET_B& b )
{
    const auto ccp = cross_cross_product(a,b) ;
    typename std::remove_const< decltype(ccp) >::type result ;

    for( auto& v : ccp ) if( v.first.second != v.second.second )
    { result.emplace( std::max( v.first, v.second ), std::min( v.first, v.second ) ) ; }

    return result ;
}

int main()
{
    std::set<int> a { 1, 2 } ;
    const std::set<char> b { 'a', 'b' } ;

    const auto print_a_cap_b = [&]
    {
        for( auto pair : operator_cap( a, b ) )
        {
            std::cout << "{ " << pair.first.first << pair.first.second << ' '
                      << pair.second.first << pair.second.second << " }  " ;
        }
        std::cout << "\n\n" ;
    };

    print_a_cap_b() ;

    a.insert(3) ;
    print_a_cap_b() ;

    {
        std::set<int> x ;
        std::set<int> y ;
        constexpr int n = 40 ;
        for( int i = 0 ; i < n ; ++i  ) { x.insert(i) ; y.insert(n+i) ; }

        const auto start = std::clock() ;
        const auto set_size = operator_cap(x,y).size() ;
        const auto end = std::clock() ;
        std::cout << "sets of " << x.size() << " elements each: result has " << set_size << " quadruples.\n"
                  << "brute force took " << double(end-start) / CLOCKS_PER_SEC << " processor seconds.\n" ;
    }
}

cpp.sh, x64:

{ 1b 1a }  { 2a 1b }  { 2b 1a }  { 2b 2a }  

{ 1b 1a }  { 2a 1b }  { 2b 1a }  { 2b 2a }  { 3a 1b }  { 3a 2b }  { 3b 1a }  { 3b 2a }  { 3b 3a }  

sets of 40 elements each: result has 1248000 quadruples.
brute force took 2.40458 processor seconds.

http://cpp.sh/3lvu5

rextester, x86:

{ 1b 1a }  { 2a 1b }  { 2b 1a }  { 2b 2a }  

{ 1b 1a }  { 2a 1b }  { 2b 1a }  { 2b 2a }  { 3a 1b }  { 3a 2b }  { 3b 1a }  { 3b 2a }  { 3b 3a }  

sets of 30 elements each: result has 391500 quadruples.
brute force took 5.533 processor seconds.

http://rextester.com/RMRR30529