Re: [ublas] combinatoric problem with vectors

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 
algorithm and the detail answer

Phil