STL and combinations question

Discussion in 'C++' started by Phil, Dec 29, 2006.

  1. Phil

    Phil Guest

    Thank you for reading my plea for help.

    What I'm trying to achieve is to get the subsets from a given set using the
    Standard Template Library.

    Say, for example, I have created an empty set and then have inserted 3
    numbers into that set (1, 2, 3). Next, I would like to get all of the subset
    pairs (1, 2), (1, 3) and (2, 3) for processing.

    A Google search has given me a lot to think about but nothing specific for
    my needs. I have played with next_permutation and read about
    next_combination which sounded more promising, since combinations are what
    I'm looking for, but next_combination doesn't appear to be part of STL (572:
    error: 'next_combination' was not declared in this scope).

    Can someone please put me on the right track? Perhaps a simple example might
    help.

    --
    Regards,
    Phil.
     
    Phil, Dec 29, 2006
    #1
    1. Advertising

  2. Phil

    John Carson Guest

    "Phil" <> wrote in message
    news:Tm%kh.15050$
    > Thank you for reading my plea for help.
    >
    > What I'm trying to achieve is to get the subsets from a given set
    > using the Standard Template Library.
    >
    > Say, for example, I have created an empty set and then have inserted 3
    > numbers into that set (1, 2, 3). Next, I would like to get all of the
    > subset pairs (1, 2), (1, 3) and (2, 3) for processing.
    >
    > A Google search has given me a lot to think about but nothing
    > specific for my needs. I have played with next_permutation and read
    > about next_combination which sounded more promising, since
    > combinations are what I'm looking for, but next_combination doesn't
    > appear to be part of STL (572: error: 'next_combination' was not
    > declared in this scope).
    > Can someone please put me on the right track? Perhaps a simple
    > example might help.



    Algorithms for finding all subsets are not trivial and have nothing
    specifically to do with the C++ language. Try

    comp.programming

    --
    John Carson
     
    John Carson, Dec 29, 2006
    #2
    1. Advertising

  3. On 2006-12-29 03:49, Phil wrote:
    > Thank you for reading my plea for help.
    >
    > What I'm trying to achieve is to get the subsets from a given set using the
    > Standard Template Library.
    >
    > Say, for example, I have created an empty set and then have inserted 3
    > numbers into that set (1, 2, 3). Next, I would like to get all of the subset
    > pairs (1, 2), (1, 3) and (2, 3) for processing.


    This can probably be done using any container but I find a vector
    particularly useful in this case:

    #include <vector>
    #include <utils>

    std::vector<int> set;
    std::vector<std::pair<int, int> > pairs;

    // initialize the set somehow

    for (size_t i = 0; i < set.size(); ++i)
    for (size_t j = i + 1; j < set.size(); ++k)
    pairs.push_back(std::make_pair(i, j));

    This will run in about O((n^2) / 2).

    --
    Erik Wikström
     
    =?ISO-8859-1?Q?Erik_Wikstr=F6m?=, Dec 30, 2006
    #3
  4. Erik Wikström wrote:
    > On 2006-12-29 03:49, Phil wrote:
    >> Thank you for reading my plea for help.
    >>
    >> What I'm trying to achieve is to get the subsets from a given set
    >> using the Standard Template Library.
    >>
    >> Say, for example, I have created an empty set and then have inserted 3
    >> numbers into that set (1, 2, 3). Next, I would like to get all of the
    >> subset pairs (1, 2), (1, 3) and (2, 3) for processing.

    >
    > This can probably be done using any container but I find a vector
    > particularly useful in this case:
    >
    > #include <vector>
    > #include <utils>
    >
    > std::vector<int> set;
    > std::vector<std::pair<int, int> > pairs;
    >
    > // initialize the set somehow
    >
    > for (size_t i = 0; i < set.size(); ++i)
    > for (size_t j = i + 1; j < set.size(); ++k)
    > pairs.push_back(std::make_pair(i, j));
    >
    > This will run in about O((n^2) / 2).



    Would boost's "next_combination" work ?

    see this:
    http://www.bxmy.org/code/combination.hpp
     
    Gianni Mariani, Dec 30, 2006
    #4
  5. On 2006-12-30 23:06, Gianni Mariani wrote:
    > Erik Wikström wrote:
    >> On 2006-12-29 03:49, Phil wrote:
    >>> Thank you for reading my plea for help.
    >>>
    >>> What I'm trying to achieve is to get the subsets from a given set
    >>> using the Standard Template Library.
    >>>
    >>> Say, for example, I have created an empty set and then have inserted 3
    >>> numbers into that set (1, 2, 3). Next, I would like to get all of the
    >>> subset pairs (1, 2), (1, 3) and (2, 3) for processing.

    >>
    >> This can probably be done using any container but I find a vector
    >> particularly useful in this case:
    >>
    >> #include <vector>
    >> #include <utils>
    >>
    >> std::vector<int> set;
    >> std::vector<std::pair<int, int> > pairs;
    >>
    >> // initialize the set somehow
    >>
    >> for (size_t i = 0; i < set.size(); ++i)
    >> for (size_t j = i + 1; j < set.size(); ++k)
    >> pairs.push_back(std::make_pair(i, j));
    >>
    >> This will run in about O((n^2) / 2).

    >
    >
    > Would boost's "next_combination" work ?
    >
    > see this:
    > http://www.bxmy.org/code/combination.hpp


    The link does not lead to code that is part of boost, and from the code
    I saw it looked unnecessarily complicated, but it might work. Best way
    to find out is to test it. You might also be interested in the
    following: http://www.codeproject.com/cpp/CombC.asp

    --
    Erik Wikström
     
    =?ISO-8859-1?Q?Erik_Wikstr=F6m?=, Dec 31, 2006
    #5
  6. In article <Tm%kh.15050$>,
    "Phil" <> wrote:

    > Thank you for reading my plea for help.
    >
    > What I'm trying to achieve is to get the subsets from a given set using the
    > Standard Template Library.
    >
    > Say, for example, I have created an empty set and then have inserted 3
    > numbers into that set (1, 2, 3). Next, I would like to get all of the subset
    > pairs (1, 2), (1, 3) and (2, 3) for processing.
    >
    > A Google search has given me a lot to think about but nothing specific for
    > my needs. I have played with next_permutation and read about
    > next_combination which sounded more promising, since combinations are what
    > I'm looking for, but next_combination doesn't appear to be part of STL (572:
    > error: 'next_combination' was not declared in this scope).
    >
    > Can someone please put me on the right track? Perhaps a simple example might
    > help.


    This question comes up often enough that I believe C++ should have a
    standard solution. I do not find a need for this functionality often.
    But I do need it sometimes. And when I need it, I really need it badly.
    And it is very non-trivial to get right.

    I most recently used the below-linked code to semi-automate the
    generation of test cases for the rvalue reference work. I needed to
    test all combinations of function calls involving lvalue and rvalue
    arguments to overload sets containing const and/or volatile lvalue and
    rvalue references (here's a link to those tests for the curious
    http://home.twcny.rr.com/hinnant/cpp_extensions/rvalue_ref_test/).

    Anyway, I've decided to make the fundamental combination (and
    permutation) algorithms public. They can be found here, including a
    couple of demoes:

    http://home.twcny.rr.com/hinnant/cpp_extensions/combinations.html

    The second demo (involving clusters of cities) is perhaps the most
    interesting. It demonstrates the ability to perform a combination
    calculation that itself involves computing over combinations.
    Admittedly the demo could be coded more efficiently. But hasn't been
    for the purpose of demonstrating this nested combination computation
    capability.

    This set of algorithms is not necessarily a complete set. But I do not
    have the time to extend it for now. I currently have:

    template<class BidirectionalIterator, class Function, class Size>
    Function
    for_each_permutation(BidirectionalIterator first,
    BidirectionalIterator last,
    Size k, Function f);


    template<class BidirectionalIterator, class Function, class Size>
    Function
    for_each_circular_permutation(BidirectionalIterator first,
    BidirectionalIterator last,
    Size k, Function f);

    template<class BidirectionalIterator, class Function, class Size>
    Function
    for_each_combination(BidirectionalIterator first,
    BidirectionalIterator last,
    Size k, Function f);

    I wouldn't mind having "reversible permutation" versions. I.e. when you
    consider a permutation and its reverse to be the same set, there's no
    need to compute characteristics of both (e.g. if you're computing the
    sum of distances between a sequence of locations, the distance is the
    same whether the locations are traversed forwards or backwards). This
    could cut the expense of the above permutation functions in half, but I
    have not succeeded in coding those algorithms at this point.

    Hth.

    -Howard
     
    Howard Hinnant, Jan 2, 2007
    #6
    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. Alex Vinokur
    Replies:
    2
    Views:
    2,840
    Alex Vinokur
    May 13, 2004
  2. Jeff Kish

    permutations and combinations

    Jeff Kish, Mar 7, 2005, in forum: C++
    Replies:
    9
    Views:
    2,296
    DHOLLINGSWORTH2
    Mar 11, 2005
  3. Replies:
    6
    Views:
    494
  4. Ben Pfaff

    Re: Combinations with true and false

    Ben Pfaff, Oct 27, 2010, in forum: C Programming
    Replies:
    7
    Views:
    900
  5. Seebs

    Re: Combinations with true and false

    Seebs, Oct 27, 2010, in forum: C Programming
    Replies:
    2
    Views:
    323
    Seebs
    Oct 28, 2010
Loading...

Share This Page