# Check is_permutation on a pair of same sized arrays – follow-up

Posted on

Problem

After considering the suggestions of my previous question, Check whether given a pair of arrays are permutation of each other, I changed the code.

• Resolved the bug reported earlier
• In place of std::set using std::unordered_map to attain O(n)$O\left(n\right)$$O(n)$ complexity
• In place of indexing array used std::array
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<array>
template <typename T1, std::size_t N>
std::unordered_map<int,int> make_unordered_map(std::array<T1,N> & array)
{
std::unordered_map<int,int> temp_unordered_map;
auto temp_unordered_map_end = temp_unordered_map.end();
for( auto &x: array)
{
auto it_temp_unordered_map = temp_unordered_map.find(x);
if( it_temp_unordered_map == temp_unordered_map_end)
{
temp_unordered_map.insert(std::pair<T1,int>(x,1));
}
else
{
++(it_temp_unordered_map->second);
}
}
return temp_unordered_map;
}

template <typename T1, std::size_t N1, std::size_t N2>
bool is_permutation(std::array<T1,N1> & array1, std::array<T1,N2>&  array2)
{
if( N1  != N2)
return false;
else
{
std::unordered_map<int,int> first_map = make_unordered_map(array1);
std::unordered_map<int,int> second_map = make_unordered_map(array2);

std::pair<std::unordered_map<int,int>::iterator,std::unordered_map<int,int>::iterator> myPair=
std::mismatch(first_map.begin(),first_map.end(),second_map.begin(),
[](std::pair<const int,int>& seed1, std::pair<const int,int> & seed2)
{ return seed1.second == seed2.second;}
);

if(( myPair.first == first_map.end()) && (myPair.second == second_map.end()))
return true;
else
return false;
}
}

int main()
{
std::array<int,5> array1 {{1,3,1,4,5}};
std::array<int,4> array2 {{1,1,4,3}};

if(::is_permutation<int,array1.size(), array2.size()>(array1, array2))
std::cout<< " Arrays are permutation of each othern";
else
std::cout<< " Arrays are not permutation of each othern";

return 0;
}


Solution

# Genericity

Your algorithm currently only works for std::array and nothing else, which is a little bit sad: you could make it work for other sequence containers as well. You could improve this by making you algorithm take two pairs of iterators like the C++14 version of std::is_permutation:

template <typename ForwardIterator1, typename ForwardIterator2>
bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);


Note that I used forward iterators since the operations you use do not require anything more specialized to work.

You will have to make some compromises like using std::distance to check whether the sizes are the same, which eventually means that the size comparison will only be O(n)$O\left(n\right)$$O(n)$ for random-access iterators. In a future C++ world with concepts and a standardized std::size, you could have a signature like this:

bool is_permutation(const ForwardIterable& cont1,
const ForwardIterable& cont2);


Here, I used the ForwardIterable concept which represents types that have forward iterators. You could then use std::size to compute the size of the container; for std::list, you would have a size in O(1)$O\left(1\right)$$O(1)$ for example while it does not have random-access iterators.

However, we’re still stuck in a world without concepts. We can emulate concept constraints but it gets pretty messy, so let’s stuck to the iterator version for now even if it means that it won’t be optimal.

# Smaller concrete things

A few things easy to change that may make you smile:

• If you intend to go the genericity way, then use std::begin and std::end instead of the begin and end functions since the former will work on more sequence containers.

• These lines could be improved:

if(( myPair.first == first_map.end()) && (myPair.second == second_map.end()))
return true;
else
return false;


First, it’s better to always use braces with if and other control structures to avoid small and silent errors in the future. But in this case, you can actually get rid of the condition altogether:

return myPair.first == first_map.end()
&& myPair.second == second_map.end();

• Having to deal with std::pair whenever you want to use std::map and friends can be bothersome. Fortunately, there are ways to hide them. For example, you can change this line:

temp_unordered_map.insert(std::pair<T1,int>(x,1));


into this one:

temp_unordered_map.emplace(x, 1);

• The function make_unordered_map does not tell much more than its return type. The name count_occurrences would probably be more suitable and provide more information.

• If you plan to keep your function working only for std::array, then you can actually get rid of this runtime check:

if( N1  != N2)


You can replace it by a compile-time static_assert to warn users that they are doing something bad right from the start:

static_assert(N1 == N2, "is_permutation only accepts arrays of the same size");


I modified the code to include a few of suggestions from the given answer:

#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<array>
#include<type_traits>

template <typename T1, std::size_t N>
std::unordered_map<int,int> count_frequency(std::array<T1,N> & array)
{
std::unordered_map<int,int> temp_unordered_map;
auto temp_unordered_map_end = std::end(temp_unordered_map);
for( auto &x: array)
{
auto it_temp_unordered_map = temp_unordered_map.find(x);
if( it_temp_unordered_map == temp_unordered_map_end)
{
temp_unordered_map.emplace(x,1);
}
else
{
++(it_temp_unordered_map->second);
}
}
return temp_unordered_map;
}

template <typename T1, std::size_t N1, std::size_t N2>
bool is_permutation(std::array<T1,N1> & array1, std::array<T1,N2>&  array2)
{
static_assert(N1==N2, "is_permutation accepts same size arrays");

std::unordered_map<int,int> first_map = count_frequency(array1);
std::unordered_map<int,int> second_map = count_frequency(array2);

std::pair<std::unordered_map<int,int>::iterator,std::unordered_map<int,int>::iterator> myPair=
std::mismatch(std::begin(first_map),std::end(first_map),std::begin(second_map),
[](std::pair<const int,int>& seed1, std::pair<const int,int> & seed2)
{ return seed1.second == seed2.second;}
);

return  myPair.first == first_map.end() && myPair.second == second_map.end();
}

int main()
{
std::array<int,4> array1 {{1,3,1,4}};
std::array<int,4> array2 {{1,1,4,3}};

if(::is_permutation<int,array1.size(), array2.size()>(array1, array2))
std::cout<< " Arrays are permutation of each othern";
else
std::cout<< " Arrays are not permutation of each othern";

return 0;
}