generate a string

I'm trying to generate a string that represents a sum of products expression.

Here are some examples of strings for various degrees:

// degree = 2

if (t >= knot[i] && t <= knot[i+1] && knot[i] != knot[i+1]){

d = a(i,k);

}

elseif (t >= knot[i+1] && t <= knot[i+2] && knot[i+1] != knot[i+2]){

d = b(i,k);

}

// degree = 3

if (t >= knot[i] && t <= knot[i+1] && knot[i] != knot[i+1]){

d = a(i,k)*a(i,k-1);

}

elseif (t >= knot[i+1] && t <= knot[i+2] && knot[i+1] != knot[i+2]){

d = a(i,k)*b(i,k-1) + b(i,k)*a(i+1,k-1);

}

elseif (t >= knot[i+2] && t <= knot[i+3] && knot[i+2] != knot[i+3]){

d = b(i,k)*b(i+1,k-1);

}

// degree = 4

if (t >= knot[i] && t <= knot[i+1] && knot[i] != knot[i+1]){

d = a(i,k)*a(i,k-1)*a(i,k-2);

}

elseif (t >= knot[i+1] && t <= knot[i+2] && knot[i+1] != knot[i+2]){

d = a(i,k)*a(i,k-1)*b(i,k-2) + a(i,k)*b(i,k-1)*a(i+1,k-2) + b(i,k)*a(i+1,k-1)*a(i+1,k-2);

}

elseif (t >= knot[i+2] && t <= knot[i+3] && knot[i+2] != knot[i+3]){

d = a(i,k)*b(i,k-1)*b(i+1,k-2) + b(i,k)*a(i+1,k-1)*b(i+1,k-2) + b(i,k)*b(i+1,k-1)*a(i+2,k-2);

}

elseif (t >= knot[i+3] && t <= knot[i+4] && knot[i+3] != knot[i+4]){

d = b(i,k)*b(i+1,k-1)*b(i+2,k-2);

}

// degree = 5

if (t >= knot[i] && t <= knot[i+1] && knot[i] != knot[i+1]){

d = a(i,k)*a(i,k-1)*a(i,k-2)*a(i,k-3);

}

elseif (t >= knot[i+1] && t <= knot[i+2] && knot[i+1] != knot[i+2]){

d = a(i,k)*a(i,k-1)*a(i,k-2)*b(i,k-3) + a(i,k)*a(i,k-1)*b(i,k-2)*a(i+1,k-3) + a(i,k)*b(i,k-1)*a(i+1,k-2)*a(i+1,k-3) + b(i,k)*a(i+1,k-1)*a(i+1,k-2)*a(i+1,k-3);

}

elseif (t >= knot[i+2] && t <= knot[i+3] && knot[i+2] != knot[i+3]){

d = a(i,k)*a(i,k-1)*b(i,k-2)*b(i+1,k-3) + a(i,k)*b(i,k-1)*a(i+1,k-2)*b(i+1,k-3) + a(i,k)*b(i,k-1)*b(i+1,k-2)*a(i+2,k-3) + b(i,k)*a(i+1,k-1)*a(i+1,k-2)*b(i+1,k-3) + b(i,k)*a(i+1,k-1)*b(i+1,k-2)*a(i+2,k-3) + b(i,k)*b(i+1,k-1)*a(i+2,k-2)*a(i+2,k-3);

}

elseif (t >= knot[i+3] && t <= knot[i+4] && knot[i+3] != knot[i+4]){

d = a(i,k)*b(i,k-1)*b(i+1,k-2)*b(i+2,k-3) + b(i,k)*a(i+1,k-1)*b(i+1,k-2)*b(i+2,k-3) + b(i,k)*b(i+1,k-1)*a(i+2,k-2)*b(i+2,k-3) + b(i,k)*b(i+1,k-1)*b(i+2,k-2)*a(i+3,k-3);

}

elseif (t >= knot[i+4] && t <= knot[i+5] && knot[i+4] != knot[i+5]){

d = b(i,k)*b(i+1,k-1)*b(i+2,k-2)*b(i+3,k-3);

}

I have figured out everything except how the values inside the a() function change.

Here is my current code that generates the strings.

publicclass Test{

publicstaticvoid main(String[] args){

int degree = 5;

for (int j = 0; j < degree; j++){

//int a = i+j;

//int b = i+j+1;

//if (t >= knot[a] && t <= knot[b] && knot[a] != knot[b]) {

int numBits = degree - 1;

int max = 1;

while (numBits-- >= 1)

max *= 2;

System.out.println("");

String s ="";

int x = degree - 1;

for (int k = 0; k < max; k++){

int bits = 0;

for (int m = 0; m < degree - 1; m++){

if (((k >> m) & 0x00000001) != 0)

bits++;

}

if (bits == j){

int bc = 0;

for (int m = 0; m < degree - 1; m++){

if (((k >> m) & 0x00000001) != 0){

s +="b(i+" + (bc++) +",k-" + m +")";

}

else{

s +="a(i+" +"?" +",k-" + m +")";

}

}

s +=" + ";

}

}

System.out.println(s);

//break;

//}

}

}

}

[7276 byte] By [rkippena] at [2007-10-1 9:13:56]
# 1
I should have put in the first post that the purpose of this is to transform a recursive algorithm into a non-recursive one.The recursive definition is given by:n(i,k) = a(i,k) * n(i,k-1) + b(i,k) * n(i+1, k-1)n(i,1) = 0 or 1 depending on i.k is the degree.
rkippena at 2007-7-10 1:38:39 > top of Java-index,Other Topics,Algorithms...
# 2

Actually, I think I found the pattern by looking at degree 6:

0 0 0 0 0

0 0 0 0

0 0 0 1

0 0 1 1

0 1 1 1

1 1 1 1

0 0 0

0 0 1

0 0 2

0 1 1

0 1 2

0 2 2

1 1 1

1 1 2

1 2 2

2 2 2

--

0 0

0 1

0 2

0 3

1 1

1 2

1 3

2 2

2 3

3 3

0

1

2

3

4

-

Hard to explain, but when the counter overflows, the bits get reset, but all the bits get reset to the value of the leftmost bit that was overflowed to.

rkippena at 2007-7-10 1:38:39 > top of Java-index,Other Topics,Algorithms...
# 3

Here's the algorithm to generate the values inside the a function:

public class ACount {

public static void main(String[] args) {

int degree = 5;

int[] count = new int[degree];

for (int m = 0; m < degree; m++) {

for (int j = degree - m - 1; j >= 0; j--)

count[j] = 0;

while (true) {

int i = 0;

boolean reset = false;

for (int j = degree - m - 1; j >= 0; j--) {

System.out.print(count[j] + " ");

}

System.out.println();

int k = 0;

for (; k < degree - m; k++)

if (count[k] != m)

break;

if (k == degree - m) break;

while (true) {

count[i]++;

if (count[i] > m) {

i++;

reset = true;

}

else {

if (reset) {

for (int j = i - 1; j >= 0; j--)

count[j] = count[i];

}

break;

}

}

}

System.out.println("--");

}

}

}

rkippena at 2007-7-10 1:38:39 > top of Java-index,Other Topics,Algorithms...