Back
Download the header File
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
// a macro that counts the nuber of elements in a C style array.
#define NELEMS(A) ( sizeof(A)/sizeof(A[0]) )
// this function prints out the return vector in a way that you can see how many there are,
// and what they are.
template< class TYPE >
ostream& operator<<( ostream& os, vector< vector < TYPE > >& toBeOutputed)
{
int num = 1;
for (int i = 0; i < toBeOutputed.size(); ++i)
{
os << num++ << " ---- ";
for (int j = 0; j < toBeOutputed[i].size(); ++j)
{
os << toBeOutputed[i][j];
}
os << endl ;
}
return os;
}
template< class TYPE >
void permutateNofR
(
vector< TYPE >& source, // this is the bag of things to be used for permutating
vector< vector< TYPE > >& destination, // this is the double vector that is used to hold all the permutations
int num, // this is the number of things to pull out of the bag
vector< int >* indexesToIgnore = NULL, // this is a vector of integers pointer to the spots of elements you don't want put in the solution
vector< TYPE >* stub = NULL // this is the starting stub - all entries will have this information at the beginning of it.
)
{
// this creates the "stub" vector if there isn't one.
if ( stub == NULL )
{
stub = new vector< TYPE >;
}
// this creates the "indexesToIgnore" vector if there isn't one
if ( indexesToIgnore == NULL )
{
indexesToIgnore = new vector< int >;
}
// loop through all of the source elements
for( int i = 0; i < source.size(); ++i)
{
// continue on used indexes so you will not duplicate them
if ( find( indexesToIgnore->begin(), indexesToIgnore->end(), i ) != indexesToIgnore->end() )
{
continue;
}
// tack on to the stub your contribution to the solution
stub->push_back( source[i] );
// if you are NOT the last function in the call chain
if ( num > 1)
{
indexesToIgnore->push_back( i ); // set your 'i' as a used iterator
permutateNofR( source, destination, num - 1, indexesToIgnore, stub ); // continue with the rest of the slots for 'stub'
indexesToIgnore->pop_back( ); // pull off your i as used,
}
else
{
destination.push_back( (*stub) ); // push a final solution on the the return vector
}
// pull of your contribution to stub
stub->pop_back( );
}
}
/* A little math to help you undestand how many solutions you should have.
n!
----------
(n! - r!)
n = number of them
r = selections
5!
---------- = 5!/2! = ( 5 * 4 * 3 * 2 * 1 ) / ( 2 * 1 ) = 120/2 = 60
(5 - 3)!
so if you have a bag with 5 different items in it,
and you want to find out how many different ways you can pull
3 items out of the bag, the answer is 60
for your own calculations remember that 0! = 1 -- you may need it.
*/
void main(void)
{
// create the source vector
char initLetters[] = { 'A', 'B', 'C', 'D', 'E' };
vector< char > letters( initLetters, initLetters + NELEMS(initLetters) );
// create the return vector
vector< vector< char > > threeLetterWords;
// this vector tells the function to exclude indexes 0 and 4 (Letters A and E)
int excludedLetterIndexes[] = { 0, 4 };
vector< int > toBeExcluded(excludedLetterIndexes, excludedLetterIndexes + NELEMS(excludedLetterIndexes) );
// the Stub has the letter X in it
vector< char > stub;
stub.push_back( 'X' );
// Plain Call
permutateNofR( letters, threeLetterWords, 3);
cout << "There are " << threeLetterWords.size() << " Solutions to the plain call." << endl;
// Uncomment this line to see all the solutions
//cout << threeLetterWords;
threeLetterWords.clear(); // Clear the return vector
// Call with exclusions,
permutateNofR( letters, threeLetterWords, 3, &toBeExcluded);
cout << "There are " << threeLetterWords.size() << " Solutions to the Call with exclusions." << endl;
// Uncomment this line to see all the solutions
//cout << threeLetterWords;
// Clear the return vector
threeLetterWords.clear();
// Call with the Stub
permutateNofR( letters, threeLetterWords, 3, NULL, &stub);
cout << "There are " << threeLetterWords.size() << " Solutions to the Call with the Stub." << endl;
// Uncomment this line to see all the solutions
//cout << threeLetterWords;
threeLetterWords.clear(); // Clear the return vector
permutateNofR( letters, threeLetterWords, 3, &toBeExcluded, &stub); // Call with stub and exclusions
cout << "There are " << threeLetterWords.size() << " Solutions to the Call with stub and exclusions." << endl;
// Uncomment this line to see all the solutions
//cout << threeLetterWords;
}