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

Discussion in 'C++' started by Eric BÃ¶se-Wolf, Jan 11, 2010.

1. ### Eric BÃ¶se-WolfGuest

sherman writes:

> On 11 Jan 2010 10:37:14 +0200, Jussi Piitulainen
> <> 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++?

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) );
}
result.push_back( perm );

//increment the state
typename std::vector<element>::size_type i = count - 1;
++(state);
while( state == elements.end() ) {
if( i == 0 ) break;
state = elements.begin();
i = i - 1;
++(state);
}
}

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

Eric BÃ¶se-Wolf, Jan 11, 2010

2. ### MensanatorGuest

On Jan 11, 2:36 pm, (Eric Böse-Wolf) wrote:
> sherman writes:
> > On 11 Jan 2010 10:37:14 +0200, Jussi Piitulainen
> > <> 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) );
>         }
>         result.push_back( perm );
>
>         //increment the state
>         typename std::vector<element>::size_type i = count - 1;
>         ++(state);
>         while( state == elements.end() ) {
>             if( i == 0 ) break;
>             state = elements.begin();
>             i = i - 1;
>             ++(state);
>         }
>     }
>
>     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 ....

Yes, but don't let Jussi's example sway you, it's built in now.

>>> import itertools as it
>>> for i in it.permutations('abc',2): print(i)

('a', 'b')
('a', 'c')
('b', 'a')
('b', 'c')
('c', 'a')
('c', 'b')

>
> Yours sincerely
>
> Eric

Mensanator, Jan 11, 2010

3. ### Christopher DearloveGuest

"Eric "Böse-Wolf"" <> wrote in message
news:...
> 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?

I had a mental lapse when I suggested std::next_permutation, I was
forgetting that when I used it for this problem in a program I have,
I was actually using an extension to it described in n2639, which
was proposed in 2008 for C++ standardisation. (I have at least one
suggested addition to those functions, should that proposal get
revived in a TC.)

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2639.pdf

It's the next_partial_permutation that's wanted - and there is example
code to implement it using next_permuation. There is also combination
code as well.

Christopher Dearlove, Jan 12, 2010
4. ### Eric BÃ¶se-WolfGuest

The proposed algorithm does not computer permutations or
combinations, but all permutations with repitions.

yours

eric

Eric BÃ¶se-Wolf, Jan 12, 2010
5. ### Eric BÃ¶se-WolfGuest

Hi Christopher,

"Christopher Dearlove" <> writes:

> "Eric "BÃ¶se-Wolf"" <> wrote in message
> news:...
>> 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?

>
>
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2639.pdf

That was a great reading. Thanks for the hint.

I can say that my algorithm and the standard and/or proposed standard
algorithms do different things. Mine uses the order in the list of
elements as ordering and starts with the lexicographically smallest
permutation according to this order and generates all permutations from
there on.

The standard algorithms are handed a permutation and an ordering
(implement not by a list or iterator range but by the assumptions, that
the elements of the permutation, which was handed over, are
LessThenComparable) and generates the lexicographically next
permutation.

Eric

Eric BÃ¶se-Wolf, Jan 13, 2010
6. ### Christopher DearloveGuest

"Eric "Böse-Wolf"" <> wrote in message
news:...
> I can say that my algorithm and the standard and/or proposed standard
> algorithms do different things. Mine uses the order in the list of
> elements as ordering and starts with the lexicographically smallest
> permutation according to this order and generates all permutations from
> there on.
>
> The standard algorithms are handed a permutation and an ordering
> (implement not by a list or iterator range but by the assumptions, that
> the elements of the permutation, which was handed over, are
> LessThenComparable) and generates the lexicographically next
> permutation.

I think the proposed (I don't know if still proposed, but I'd support it
for a TC - with, as I noted, at least one addition) algorithm is a more
appropriate addition to the standard, both for being a natural extension
to std::next_permutation and fitting the general STL framework. Of
course for your purposes, what's appropriate is what works for you.

Christopher Dearlove, Jan 18, 2010
7. ### Eric BÃ¶se-WolfGuest

"Christopher Dearlove" <> writes:

> "Eric "BÃ¶se-Wolf"" <> wrote in message
> news:...
>> I can say that my algorithm and the standard and/or proposed standard
>> algorithms do different things. Mine uses the order in the list of
>> elements as ordering and starts with the lexicographically smallest
>> permutation according to this order and generates all permutations from
>> there on.
>>
>> The standard algorithms are handed a permutation and an ordering
>> (implement not by a list or iterator range but by the assumptions, that
>> the elements of the permutation, which was handed over, are
>> LessThenComparable) and generates the lexicographically next
>> permutation.

>
> I think the proposed (I don't know if still proposed, but I'd support it
> for a TC - with, as I noted, at least one addition) algorithm is a more
> appropriate addition to the standard, both for being a natural extension
> to std::next_permutation and fitting the general STL framework. Of
> course for your purposes, what's appropriate is what works for you.

I never meant to propose something for standardization.

Eric BÃ¶se-Wolf, Jan 18, 2010