Re: All Permutations of 10 Things taken 7 at a Time?

sherman writes:


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