# Ublas :

Subject: Re: [ublas] combinatoric problem with vectors
From: Philipp Kraus (philipp.kraus_at_[hidden])
Date: 2010-12-06 04:41:05

On 2010-12-05 19:17:56 +0100, Matthias Walter said:

> On 12/05/2010 12:27 PM, Philipp Kraus wrote:
>> On 2010-12-05 18:07:55 +0100, Matthias Walter said:
>>
>>> On 12/05/2010 11:51 AM, Philipp Kraus wrote:
>>>> On 2010-12-05 17:25:57 +0100, Matthias Walter said:
>>>>
>>>>> On 12/05/2010 11:08 AM, Kraus Philipp wrote:
>>>>>> I have n ublas vectors with different sizes. Now I would create a
>>>>>> ublas matrix with n columns in that way, that each row has a
>>>>>> combination of the vector elements. I need all combination of the
>>>>>> vector elements (I know it is an exponential problem, but my vectors
>>>>>> are small).
>>>>> Can you be a bit more precise? How does a "combination of the vector
>>>>> elements" look like, especially when they are of different sizes?
>>>>> Maybe
>>>>> a small example with 2 or 3 vectors would help.
>>>>
>>>>
>>>> for two vectors with different size [1] & [2 3]
>>>>
>>>> 1 2
>>>> 1 3
>>>>
>>>> with equal size [1 2] & [3 4]
>>>>
>>>> 1 3
>>>> 1 4
>>>> 2 3
>>>> 2 4
>>>>
>>>> I hope I have written all combination :-)
>>>> Each element of each vector should be combinate with the elements of
>>>> the others
>>> Ah, that makes sense now :) One has to read the matrix as a collection
>>> of row-vectors...
>>>
>>> Last question before I'd answer: Do you want all combinations or only a
>>> specific set?
>> I would combine all sets, also [1 2] is not the same like [2 1] both
>> combinations must add to the set.
> Okay, then it is relatively easy:
>
> You can generate the rows recursively. As the height of the matrix
> equals the product of all vector's sizes, you can preallocate the matrix
> and the add the vectors one by one. The following scheme should work:
>
> function combine(v, k)
> if k < #vectors
> for i = 0 to size(v_k)-1
> v[k] = v_k[i];
> combine(v, k+1);
> else
> add v as a row to the matrix;
>
> create v;
> combine(v, 0);
>
> v shall be passed by reference and is our "working vector" which get's
> filled. Each call to combine then takes care of one of your input
> vectors (the k-th one), choosing all possible values, one after another.
> And each choice calls combine for the next column to combine this choice
> with all further vector-choices.
>
> That would be an easy algorithm. If you have specific questions on the
> implementation, just let us know.

Thanks, I have create the recursive algorithm, but it's nice, that you
posted it, but it would been enough to answer, that the Boost supports
merge-operations for do the combinatoric merge. Thanks a lot for the