454,445 Members | 1,329 Online Need help? Post your question and get tips & solutions from a community of 454,445 IT Pros & Developers. It's quick & easy.

# C++ algorithm for combinations of vector elements

 P: n/a 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 Nov 1 '05 #1
8 Replies

 P: n/a "cayblood" wrote in message news:11********************@z14g2000cwz.googlegrou ps.com... 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>::interator OuterIt; std::vector::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. Nov 1 '05 #2

 P: n/a 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 Nov 1 '05 #3

 P: n/a But do you have any ideas on how to make it work for arbitrarily-deep levels of nesting? Nov 1 '05 #4

 P: n/a 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. Nov 1 '05 #5

 P: n/a 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 Nov 1 '05 #6

 P: n/a >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. Nov 1 '05 #7

 P: n/a 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 Nov 1 '05 #8

 P: n/a 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 Nov 2 '05 #9

### This discussion thread is closed

Replies have been disabled for this discussion. 