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

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

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

    Yours sincerely

    Eric
    Eric Böse-Wolf, Jan 11, 2010
    #1
    1. Advertising

  2. Eric Böse-Wolf

    Mensanator Guest

    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.

    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
    Mensanator, Jan 11, 2010
    #2
    1. Advertising

  3. "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
    #3
  4. The proposed algorithm does not computer permutations or
    combinations, but all permutations with repitions.

    yours

    eric
    Eric Böse-Wolf, Jan 12, 2010
    #4
  5. 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
    #5
  6. "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
    #6
  7. "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
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ike
    Replies:
    3
    Views:
    1,040
    opalinski from opalpaweb
    Jan 23, 2006
  2. Gunnar G

    find all permutations

    Gunnar G, Sep 12, 2004, in forum: C++
    Replies:
    2
    Views:
    489
    Kai-Uwe Bux
    Sep 12, 2004
  3. =?Utf-8?B?V2lsbGlhbSBTdWxsaXZhbg==?=

    vs2005 publish website doing bad things, bad things

    =?Utf-8?B?V2lsbGlhbSBTdWxsaXZhbg==?=, Oct 25, 2006, in forum: ASP .Net
    Replies:
    1
    Views:
    596
    =?Utf-8?B?UGV0ZXIgQnJvbWJlcmcgW0MjIE1WUF0=?=
    Oct 25, 2006
  4. Alf P. Steinbach
    Replies:
    2
    Views:
    1,430
    John H.
    Jan 11, 2010
  5. Balog Pal
    Replies:
    2
    Views:
    342
    Balog Pal
    Jan 11, 2010
Loading...

Share This Page