Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Re: All Permutations of 10 Things taken 7 at a Time?

Reply
Thread Tools

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

 
 
Eric Böse-Wolf
Guest
Posts: n/a
 
      01-11-2010
sherman writes:

> On 11 Jan 2010 10:37:14 +0200, Jussi Piitulainen
> <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
 
Mensanator
Guest
Posts: n/a
 
      01-11-2010
On Jan 11, 2:36*pm, (E-Mail Removed) (Eric Bse-Wolf) wrote:
> sherman writes:
> > On 11 Jan 2010 10:37:14 +0200, Jussi Piitulainen
> > <(E-Mail Removed)> 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 ....


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

Try this, instead.

>>> 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


 
Reply With Quote
 
 
 
 
Christopher Dearlove
Guest
Posts: n/a
 
      01-12-2010
"Eric "Bse-Wolf"" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> 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/wg...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.


 
Reply With Quote
 
Eric Böse-Wolf
Guest
Posts: n/a
 
      01-12-2010
The proposed algorithm does not computer permutations or
combinations, but all permutations with repitions.

yours

eric
 
Reply With Quote
 
Eric Böse-Wolf
Guest
Posts: n/a
 
      01-13-2010
Hi Christopher,

"Christopher Dearlove" <(E-Mail Removed)> writes:

> "Eric "Böse-Wolf"" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed)...
>> 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/wg...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
 
Reply With Quote
 
Christopher Dearlove
Guest
Posts: n/a
 
      01-18-2010
"Eric "Bse-Wolf"" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> 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.


 
Reply With Quote
 
Eric Böse-Wolf
Guest
Posts: n/a
 
      01-18-2010
"Christopher Dearlove" <(E-Mail Removed)> writes:

> "Eric "Böse-Wolf"" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed)...
>> 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.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: All Permutations of 10 Things Taken 7 at a Time? Balog Pal C++ 2 01-11-2010 07:57 PM
Re: All Permutations of 10 Things Taken 7 at a Time? Alf P. Steinbach C++ 2 01-11-2010 07:27 PM
vs2005 publish website doing bad things, bad things =?Utf-8?B?V2lsbGlhbSBTdWxsaXZhbg==?= ASP .Net 1 10-25-2006 06:18 PM
N Things taken M at a time Ike Java 3 01-23-2006 06:19 PM
d70 transport pics.all 1600 iso hand held.all pics taken at museum of trans glasgow uk. tbm Digital Photography 2 01-14-2005 09:43 PM



Advertisments