Re: [ublas] combinatoric problem with vectors

Subject: Re: [ublas] combinatoric problem with vectors
From: Matthias Walter (xammy_at_[hidden])
Date: 2010-12-05 13:17:56

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.

Matthias