Need help with this simple Algorithm

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 b is a new array. 

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];

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!

12 个解决方案

#1

function   genArray(a,d) 
{
    if d=1
      return a
    else
      return genArray(a,d-1) + genArray(a,d-1)*a
}

#2

上面的有多余的结果:)

#3

嗯，看后面的乘法怎么定义了，，，

#4

设a的元素个数为n;
b内长度（a1*a2*a3当作长度3）为j，且以ai开头的元素的个数记为c(i,j);

那么b的元素个数有递归式：
c(1,1)==c(1,2)==c(1,3)==....==c(n,1)==1;
b(1)=c(1,1)+c(1,2)+c(1,3)+...+c(n,1)==n;

...

c(i,j)==sum(c(i-1,j)...c(i-1,n)); 1<j<n
b(i)==b(i-1)+c(i,1)+c(i,2)+....+c(i,n);
....

#5

题目是求数组b;

可以按照上述的递归式来计算b的元素；

先计算d=1时新增的所有元素（a1,a2,...an)；
。。。

计算d=i时的新增元素：
1）对b中从b[i-2]+1开始的c(i,1）个元素乘a1，等到以a1开头的长度为i的元素；
2）对b中从b[i-2]+c(i,1)+1开始的c(i,2）个元素乘a2，等到以a2开头的长度为i的元素；
....
k)对b中从b[i-2]+c(i,1)+c(i,2)+...+c(i,k-1)+1开始的c(i,k）个元素乘ak，等到以ak开头的长度为i的元素；
....

#6

等到以a1开头的长度为i的元素
==>
得到所有的以a1开头的长度为i的元素

#7

#include <stdio.h> 
#include <iostream.h>

void show(int ArrayLength, int startpos, int d, int max, int* a)
{
    for(int i=startpos; i<=ArrayLength; i++)
    {
		a[d] = i;
        if(d==1) 
		{
			for(int j=max; j>=1; j--)
			{
				cout<<"×a"<<a[j];
			}
            cout<<endl;
		}
        else
		{
            show(ArrayLength, i, d-1, max, a);
		}
    } 
}

int main()
{
	int d=3;
	int *a = new int[d+1];
	for(int i=1; i<=d; i++)
	{
	    show(10, 1, i, i, a);
	}
        delete[] a;
	return 0;
}

代码写的很乱，模拟的是10取3的情况。

#8

Thank you for all your kind replies. But no code above does the exact job as described in my first post.

It's not a simple recursive problem i think.

#9

It turns out not a "simple algorithm", which involves generating combinations of multisets. Here is my solution.

#include <iostream>
#include <string>
using namespace std;

bool GoNext(int *array, int max, int degree)
{
	bool bRet = false;
	for(int i=degree-1; i>=0; i--)
	{
		if(array[i] < max)
		{
			int nValue = array[i] + 1;
			for(int j=i; j<degree; j++)
				array[j] = nValue;
			bRet = true;
			break;
		}
	}

	return bRet;
}

string ItemToStr(string *a, int *item, int size)
{
	string str = "";
	for(int i=0; i<size; i++)
	{
		if(item[i]>0)
		{
			if(str.length() > 0)
				str += "*";
			str += a[item[i]-1];
		}
	}
	return str;
}

string genArray(string* a, int size, int d)
{
	int *array = new int[d];
	for(int i=0; i<d; i++)
		array[i] = 0;

	string res = "";

	res += "[ ";
	while(GoNext(array, size, d))
	{
		string s = ItemToStr(a, array, d);
		res += s + " ";
	}
	res += "]";

	return res;
}

int main()
{
	string arrTest[] = {"a1", "a2", "a3" };
	int nSize = sizeof(arrTest)/sizeof(arrTest[0]);

	cout << "d=1:" << endl << genArray(arrTest, nSize, 1) << endl << endl;
	cout << "d=2:" << endl << genArray(arrTest, nSize, 2) << endl << endl;
	cout << "d=3:" << endl << genArray(arrTest, nSize, 3) << endl << endl;

	cout << endl;
	return 0;
}

#10

thanks, deng2000, your code is cool and works well in matlab too. But i am still wondering if there is a kind of recursive way to tackle this problem.

#11

b(1, i) = [ ai, ai+1, ..., an ]
b(2, i) = ai * b(1, i) + ai+1 * b(1, i + 1) + .... an * b(1, n)
b(d, i) = ai * b(d-1, i) + ai+1 * b(d-1, i + 1) + .... an * b(d-1, n)

genArray([a1, ... , an], d) = b(1, 1) + b(2, 1) + ... b(d, 1)

#12

fengyuanMSFT, your method is simple and great. i am glad to see so many people willing to contribute ideas...