Need help with this simple Algorithm

[cmlb]

function b=genArray(a,d)

The function genArray(a,d) has two parameters in which a is an array and d is the nonlinearity degree and the output is a new array b.

The function does the following job

For example:

a=[a1 a2 a3];

if d=1
b=[a1 a2 a3];

if d=2
b=[a1 a2 a3 a1*a1 a1*a2 a1*a3 a2*a2 a2*a3 a3*a3];

if d=3
b=[a1 a2 a3 a1*a1 a1*a2 a1*a3 a2*a2 a2*a3 a3*a3
a1*a1*a1 a1*a1*a2 a1*a1*a3 a1*a2*a2 a1*a2*a3 a1*a3*a3 a2*a2*a2 a2*a2*a3 a2*a3*a3 a3*a3*a3];

if d=4
and so on.....

I have been thinking this for a couple of days, but not able to form a solution... any ideas will be much appreciated!

[vAC]

First of all, let's count the number of array elements in each multiplication group separately.
Suppose:
n - count of elements in array a (in your example n=3);
k - number of efficients in group (i'll call it 'order', e.g. 1 for output [a1 a2 a3], 2 for output [a1*a1 a1*a2, a1*a3, a2*a2 a2*a3 a3*a3]...);

If you want to pre-allocate array b, you need to know it's size, so, number of combinations must be computed.
Number of multiplication combinations for each 'order' in your case are given by classic combinatoric formula
(urn and balls, selection with return and without order account):
C(n-1, n+k-1),
where
C(x, y) = y! / (x! * (y-x)!);

so we have:
(n+k-1)! / ((n-1)! * k!) combinations;
for n=3, k=1:
(3+1-1)! / ((3-1)! * 1!) = 3! / (2!*1!) = 6 / 2 = 3;
for n=3, k=2:
(3+2-1)! / ((3-1)! * 2!) = 4! / (2!*2!) = 24 / 4 = 6;
for n=3, k=3:
(3+3-1)! / ((3-1)! * 3!) = 5! / (2!*3!) = 120 / 12 = 10;

So, you can compute total size of array b by adding sizes of each 'order'.

Next step is filling single 'order' k with vaues.
Let's define additional k-element array ind, that represent index of elements in array a, which should be
multiplied to compute single element in b array. Let's suppose that b represent only one 'order', it's simpler.
Pseudo-cpp-code of this step will be:

ind.resize(k);
ind = [0, 0, ...0];
for (i = 0; i < C(n-1, n+k-1); i++)
{
	b[i] = 1;
	for (j = 0; j < k; j++)
	{
		b[i] *= a[ind[j]];
	}
	// generate next ind array
}

I think that you'll consider how to generate next ind

[cmlb]

hi, vAC, thank you very much for your kind solution. It makes the problem much clearer to me now.

If we suppose that k=2 in the code, my understanding is that ind should beome
[0,0]
[0,1]
[0,2]
[1,1]
[1,2]
[2,2]
in the loop

is this correct?

But i am still thinking about how to write the code to implement it. Thanks again.

[vAC]

quite right
and make this job in separate function or class method (it doesn't matter). For begin it's declaration may be looks like this:

void fill_order(int n, double *p_a, int k, double *p_b);

by n and p_a you know all about size and values a[i],
by k and p_b you know where to place results and size of array ind.
That's enought for one order filling.

Then, from outside you call this function/method for each 'order', passing the same n and p_a (in your example n=3, p_a - pointer to first element of array a=[a1 a2 a3]), and correcting k (incrementing) and p_d (should pointing to place of 'order' k in b array).
That's simplest solution.

[cmlb]

Hi, vAC, you are great !!! I have solved the problem with your help.. All the best....