sherman writes:
On 11 Jan 2010 10:37:14 +0200, Jussi Piitulainen
<jpiitula@ling.helsinki.fi> wrote:
sherman writes:
Can you guys direct me to some code that contains
a way of finding all permutations of n things taken
k at a time?
Could you please transalte it in c or c++?
As you ask for C++ I assume you know your STL.
Its a version not depending on recursion and you can easily modify it to
produce combinations instead of permutations. And it produces the
permutations in a lexicographical ordering according to the order of
"elements" below.
Maybe one could use the next_permutation algorithm from the <algorithm>
header. But ... it only produces the next permutation of a given
sequence, I don't know how to get it producing k-permutations from a set
of n elements. Maybe someone could give a hint?
Go with it:
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
template<typename element> std::vector<std::vector<element> >
permutations( std::vector<element> elements,
typename std::vector<element>::size_type count )
{
if( elements.begin() == elements.end() or elements.size() < count )
return std::vector<std::vector<element> >();
std::vector<typename std::vector<element>::iterator> state;
std::vector<std::vector<element> > result;
for(typename std::vector<element>::size_type i = 0;
i < count; ++i) {
state.push_back( elements.begin() );
}
//Here we depend on elements.begin() != elements.end(),
//for state having at least one member
while( state[0] != elements.end() ) {
//first write out a permutation
std::vector<element> perm;
for( typename std::vector<element>::size_type i = 0;
i < count; ++i ) {
perm.push_back( *(state[i]) );
}
result.push_back( perm );
//increment the state
typename std::vector<element>::size_type i = count - 1;
++(state[i]);
while( state[i] == elements.end() ) {
if( i == 0 ) break;
state[i] = elements.begin();
i = i - 1;
++(state[i]);
}
}
return result;
}
int main(int argc, char * argv[] ) {
std::vector<std::string> args( argv, argv + argc );
if( args.size() != 3 ) return 1; //usage prog <number of elements> <count>
unsigned int number_of_elements;
unsigned int count;
{ //scope away number_of_elements_stream
std::istringstream number_of_elements_stream( args[1] );
number_of_elements_stream >> number_of_elements;
}
{ //scope away count_stream;
std::istringstream count_stream( args[2] );
count_stream >> count;
}
std::vector<unsigned int> elements;
for( unsigned int i = 1; i <= number_of_elements; ++i ) {
elements.push_back( i );
}
std::vector<std::vector<unsigned int> > perms =
permutations<unsigned int>( elements, count );
for(std::vector<std::vector<unsigned int> >::iterator it = perms.begin();
it != perms.end();
++it) {
for( std::vector<unsigned int>::iterator it2 = (*it).begin();
it2 != (*it).end();) {
std::cout << *it2;
if( ++it2 != (*it).end() ) std::cout << ", ";
}
std::cout << std::endl;
}
return 0;
}
Maybe I should learn Python ....
Yours sincerely
Eric