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 multidimensional 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  
Share this Question
P: n/a

"cayblood" <ca*************@gmail.com> 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 multidimensional 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.  
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 multidimensional 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  
P: n/a

But do you have any ideas on how to make it work for arbitrarilydeep
levels of nesting?  
P: n/a

One other thingI 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.  
P: n/a

cayblood wrote: One other thingI 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  
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.  
P: n/a

On 20051101, cayblood <ca*************@gmail.com> wrote: One other thingI 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  
P: n/a

cayblood wrote: But do you have any ideas on how to make it work for arbitrarilydeep levels of nesting?
Recursion, I believe, should help.
V   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 9767
 replies: 8
 date asked: Nov 1 '05
