# C++ algorithm for combinations of vector elements

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

1. ### caybloodGuest

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

2. ### Jim LangstonGuest

"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

3. ### Victor BazarovGuest

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
4. ### caybloodGuest

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

cayblood, Nov 1, 2005
5. ### caybloodGuest

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
6. ### Victor BazarovGuest

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

>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
8. ### Neil CeruttiGuest

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
9. ### Victor BazarovGuest

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