C++ algorithm for combinations of vector elements

[cayblood]

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

[Jim Langston]

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

[Victor Bazarov]

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

[cayblood]

But do you have any ideas on how to make it work for arbitrarily-deep
levels of nesting?

[cayblood]

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.

[Victor Bazarov]

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

[cayblood]

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

[Neil Cerutti]

On 2005-11-01, cayblood <ca*************@gmail.com> 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

[Victor Bazarov]

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