Home > C++, VC++, STL > Permutation combinations in Standard C++

Permutation combinations in Standard C++

Recently one of my colleagues and also another user in MSDN forum asked a question related to this. The question is as follows…

If I have a string vector with few elements like “Nibu” “Babu” “Thomas”, how can I get all combinations of these three strings? Results should look like…

“NibuBabuThomas”
“NibuThomasBabu”
“BabuNibuThomas”
“BabuThomasNibu”
“ThomasNibuBabu”
“ThomasBabuNibu”

So in C++ there is a standard C++ algorithm function called next_permutation. Use this function on an array of sorted strings to get required result. So some sample code follows…

typedef std::string VT;
typedef std::vector< VT > VTVec;

// For dumping contents of vector to a stream
void Dump( VTVec& VecToPrint, std::ostream& stream )
{
  // Get iterator for given stream, every element will be separated with second
  // parameter.
  std::ostream_iterator<VTVec::value_type> Itr( stream, ", " );
  // Just one line to dump vector contents, no loops needed
  std::copy( VecToPrint.begin(), VecToPrint.end(), Itr );

  // Remove redundant space and bracket ( ", " ) from the end
  stream << "\b\b  \b\b\n";
}// End Dump

int _tmain(int argc, TCHAR* argv[], TCHAR* envp[])
{
  int nRetCode = 0;

  VTVec vecNames;
  vecNames.push_back("Nibu");
  vecNames.push_back("Babu");
  vecNames.push_back("Thomas");

  std::sort(vecNames.begin(), vecNames.end());

  std::cout << "\nNames before applying permutations: ";
  Dump(vecNames, std::cout);
  std::cout << std::endl;

  int Count = 0;
  while(next_permutation(vecNames.begin(), vecNames.end()))
  {
    Dump(vecNames, std::cout);
    ++Count;
  }

  std::cout << "\nFound a total of " << Count << " combinations!\n";
  return nRetCode;
}

Result is as follows…

Advertisements
  1. sanj
    May 27, 2010 at 2:34 am

    Shouldn’t there be 6 combinations?

  2. January 20, 2010 at 12:00 pm

    That was a good tip. STL is full of gems…

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: