C++ algorithm for combinations of vector elements

Discussion in 'C++' started by cayblood, Oct 31, 2005.

  1. cayblood

    cayblood Guest

    Hello, I have been interested in something kind of like the
    next_permutation from the STL algorithm library, except that I want it
    to find possible combinations of vector elements. Here is a more
    detailed example of what I want:

    Given a vector containing an arbitrary number of vectors, each of which
    contains an arbitrary number of elements, generate a new vector in
    which each element consists of one element taken from its corresponding
    inner vector. Generate all possible combinations of this new vector.

    I'm sure this is confusing, and my wording is not very good, so here is
    a concrete example of what I'm looking for:

    original vector a = [[1, 2, 3], [4, 5, 6], [7, 8]]

    first combination would be [1, 4, 7]
    next combination would be [1, 4, 8]
    next combination would be [1, 5, 7]
    next combination would be [1, 5, 8]
    next combination would be [1, 6, 7]
    next combination would be [1, 6, 8]
    next combination would be [2, 4, 7]
    next combination would be [2, 4, 8]
    next combination would be [2, 5, 7]
    next combination would be [2, 5, 8]
    next combination would be [2, 6, 7]
    next combination would be [2, 6, 8]
    next combination would be [3, 4, 7]
    next combination would be [3, 4, 8]
    next combination would be [3, 5, 7]
    next combination would be [3, 5, 8]
    next combination would be [3, 6, 7]
    last combination would be [3, 6, 8]

    If you know before coding what the size of the original vector is going
    to be, this can be accomplished with a simple set of nested loops.
    However, making it work with arbitrary sizes of vectors is harder. It
    would be even cooler if I could come up with some code that could work
    with any level of vector nesting, producing something like the boost
    library's multi-dimensional arrays for vectors with more than two
    levels of nesting.

    Any thoughts? I'm not an expert at C++ templates so this is somewhat
    difficult for me.

    Thanks,

    Carl Youngblood
     
    cayblood, Oct 31, 2005
    #1
    1. Advertising

  2. cayblood

    Jim Langston Guest

    "cayblood" <> wrote in message
    news:...
    > Hello, I have been interested in something kind of like the
    > next_permutation from the STL algorithm library, except that I want it
    > to find possible combinations of vector elements. Here is a more
    > detailed example of what I want:
    >
    > Given a vector containing an arbitrary number of vectors, each of which
    > contains an arbitrary number of elements, generate a new vector in
    > which each element consists of one element taken from its corresponding
    > inner vector. Generate all possible combinations of this new vector.
    >
    > I'm sure this is confusing, and my wording is not very good, so here is
    > a concrete example of what I'm looking for:
    >
    > original vector a = [[1, 2, 3], [4, 5, 6], [7, 8]]
    >
    > first combination would be [1, 4, 7]
    > next combination would be [1, 4, 8]
    > next combination would be [1, 5, 7]
    > next combination would be [1, 5, 8]
    > next combination would be [1, 6, 7]
    > next combination would be [1, 6, 8]
    > next combination would be [2, 4, 7]
    > next combination would be [2, 4, 8]
    > next combination would be [2, 5, 7]
    > next combination would be [2, 5, 8]
    > next combination would be [2, 6, 7]
    > next combination would be [2, 6, 8]
    > next combination would be [3, 4, 7]
    > next combination would be [3, 4, 8]
    > next combination would be [3, 5, 7]
    > next combination would be [3, 5, 8]
    > next combination would be [3, 6, 7]
    > last combination would be [3, 6, 8]
    >
    > If you know before coding what the size of the original vector is going
    > to be, this can be accomplished with a simple set of nested loops.
    > However, making it work with arbitrary sizes of vectors is harder. It
    > would be even cooler if I could come up with some code that could work
    > with any level of vector nesting, producing something like the boost
    > library's multi-dimensional arrays for vectors with more than two
    > levels of nesting.
    >
    > Any thoughts? I'm not an expert at C++ templates so this is somewhat
    > difficult for me.


    I don't see a real problem here. To iterate through all the elements of a
    vector is simple, and you don't have to know the vector size. If you were
    working with arrays it would be difficult since you then have to know, but
    with vectors you don't.

    std::vector<std::vector<int>>::interator OuterIt;
    std::vector<int>::iterator InnerIt;
    for ( OuterIt = MyVector.begin(); OuterIt != MyVector.end(); ++OuterIt)
    for ( InnerIt = (*OuterIt).begin(); InnerIt != (*OuterIt).end();
    ++InnerIt )
    // permiations

    Check syntax on the (*OuterIt).begin() etc... it might be a little off.
     
    Jim Langston, Nov 1, 2005
    #2
    1. Advertising

  3. cayblood wrote:
    > Hello, I have been interested in something kind of like the
    > next_permutation from the STL algorithm library, except that I want it
    > to find possible combinations of vector elements. Here is a more
    > detailed example of what I want:
    >
    > Given a vector containing an arbitrary number of vectors, each of
    > which contains an arbitrary number of elements, generate a new vector
    > in which each element consists of one element taken from its
    > corresponding inner vector. Generate all possible combinations of
    > this new vector.
    >
    > I'm sure this is confusing, and my wording is not very good, so here
    > is a concrete example of what I'm looking for:
    >
    > original vector a = [[1, 2, 3], [4, 5, 6], [7, 8]]
    >
    > first combination would be [1, 4, 7]
    > next combination would be [...]
    >
    > If you know before coding what the size of the original vector is
    > going to be, this can be accomplished with a simple set of nested
    > loops. However, making it work with arbitrary sizes of vectors is
    > harder. It would be even cooler if I could come up with some code
    > that could work with any level of vector nesting, producing something
    > like the boost library's multi-dimensional arrays for vectors with
    > more than two levels of nesting.
    >
    > Any thoughts? I'm not an expert at C++ templates so this is somewhat
    > difficult for me.


    There is nothing essentially 'C++' and nothing 'template' here. Given that
    you have a list of lists, initialise a list of indices to "all zeros", that
    will be the helper for your first combination. From the current combination
    (from the helper, actually), figure out the next combination. A way to do
    that is a loop from the last index towards the first, add 1, see if you
    slipped beyond the corresponing list's size. If so, reset to 0 and do the
    previous. Repeat until you reach all 0 again or the combination is the
    last one (whatever suits you).

    helper = 0; // reset all helper elements
    while (combination_is_valid(helper)) {
    print_out_combination(helper);
    to_increment = last;
    while (to_increment > 0 && ++helper[to_increment] ==
    list[to_increment].size())
    helper[to_increment--] = 0;
    }

    V
     
    Victor Bazarov, Nov 1, 2005
    #3
  4. cayblood

    cayblood Guest

    But do you have any ideas on how to make it work for arbitrarily-deep
    levels of nesting?
     
    cayblood, Nov 1, 2005
    #4
  5. cayblood

    cayblood Guest

    One other thing--I wanted to write a template for this so that it would
    be as generic as the STL permutation routines and would work on any
    applicable container rather than just vectors.
     
    cayblood, Nov 1, 2005
    #5
  6. cayblood wrote:
    > One other thing--I wanted to write a template for this so that it
    > would be as generic as the STL permutation routines and would work on
    > any applicable container rather than just vectors.


    Write it twice, once for a set of lists and for a list of vectors.
    That should give you an excellent idea how to generalise the algo.

    V
     
    Victor Bazarov, Nov 1, 2005
    #6
  7. cayblood

    cayblood Guest

    >Write it twice, once for a set of lists and for a list of vectors.
    >That should give you an excellent idea how to generalise the algo.
    >V


    Thanks for the advice. Will do.
     
    cayblood, Nov 1, 2005
    #7
  8. cayblood

    Neil Cerutti Guest

    On 2005-11-01, cayblood <> wrote:
    > One other thing--I wanted to write a template for this so that
    > it would be as generic as the STL permutation routines and
    > would work on any applicable container rather than just
    > vectors.


    See if you can find a copy of _Accelerated C++_ in a library or
    bookstore. It contains what you need.

    In short, write your algorithm to use iterators. Make sure to use
    the most restrictive form of iterator you can. You should be able
    to accomplish this algorithm with forward iterators (they support
    only ++ and ==), which means it will be compatible with most
    sequences.

    --
    Neil Cerutti
     
    Neil Cerutti, Nov 1, 2005
    #8
  9. cayblood wrote:
    > But do you have any ideas on how to make it work for arbitrarily-deep
    > levels of nesting?
    >


    Recursion, I believe, should help.

    V
     
    Victor Bazarov, Nov 2, 2005
    #9
    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. jose luis fernandez diaz

    Combinations/permutations algorithm in C++

    jose luis fernandez diaz, Apr 13, 2004, in forum: C++
    Replies:
    6
    Views:
    14,121
    Leor Zolman
    Apr 13, 2004
  2. Peter R
    Replies:
    2
    Views:
    7,420
    Alex Vinokur
    May 11, 2004
  3. Replies:
    0
    Views:
    3,123
  4. deancoo
    Replies:
    2
    Views:
    430
    deancoo
    Feb 25, 2005
  5. Replies:
    8
    Views:
    1,935
    Csaba
    Feb 18, 2006
Loading...

Share This Page