Thread: how to solve this problem?

1. how to solve this problem?

If k is known before running the program, then it is easy to write codes to do the following (paragraph 2). But now k is input from keyboard. It is difficult to write codes. Are there some nice way to do this? Thank you very much.
Code:
```while(1)
{
part 1. lambda=...;
part 2. some codes relates to lambda; when lambda satisfies some conditions; break;
}```
I would like lambda take following values (in lexicographic order, a value each time, for example, lambda=lambda, then do part 2 above, and then lambda=lambda-2a[1], then do part 2 above, and so on):
lambda,
lambda-a[1], lambda-a[2], ..., lambda-a[k-1], (the sum of coefficients of a[i] is -1)
lambda-2a[1], lambda-a[1]-a[2], lambda-a[1]-a[3], ..., lambda-a[1]-a[k-1], lambda-2a[2], lambda-a[2]-a[3], ..., lambda-a[2]-a[k-1], ..., lambda-a[k-2]-a[k-1], lambda-2a[k-1], (the sum of coefficients of a[i] is -2)
lamdba-3a[1], ... (the sum of coefficients of a[i] is -3)
...

2. So that's two loops then, one for the index variable inside the a[], and the other for the multiplier out front.

3. Thank you. But it does not work, since k is unknown before we input it.

4. Originally Posted by lijr07
But it does not work, since k is unknown before we input it.
Once there is input, its value is known, so what is the problem?

5. I kind of see what you mean, maybe -- for some reason I thought you were going down columns not across. I don't know why I thought that.

You _almost_ have a combination-generation problem (since you can have duplicates), but I suspect you can easily adapt a combination-generation algorithm (like the traditional odometer-style algorithm: increment the last number until you get to the max, then add one to the previous and "roll over" the new number).

Note that you can make a vector that will resize itself as you go, so you can, at the beginning of the loop, push_back another number and now you've got 4 coefficients to play with instead of 3 (for instance).

6. Thank you very much.

we have to write the code before we know exact value of k. If we know k=2 for example, it is easy to write the code as:

Code:
```int c[2]; //k=2
int n;

// n, a[i] are known

while(1)
{

for(c[0]=0; c[0]<n; c[0]++)
{

for(c[1]=0; c[1]<n-c[0]; c[1]++) //c[0] + c[1] = n
{
for(i=0; i<2; i++)
{
lambda=lambda-c[i]*a[i]; //this loop computes lambda-c[0]*a[0]-...-c[k-1]*a[k-1]
}

{this part have some other codes relates to lambda}

if lambda satisfies some conditions, break;

}

if lambda satisfies some conditions, break;

}

if lambda satisfies some conditions, break;

}```

but now k is unknown (if k is known, we can write k loops), so I don't know how to write the codes with arbitrary k.

7. Thank you very much. But the problem is not about resize a vector. It is resize the number of loops. This is difficult. Do you have some method to solve this problems?

8. Originally Posted by tabstop
I kind of see what you mean, maybe -- for some reason I thought you were going down columns not across. I don't know why I thought that.

You _almost_ have a combination-generation problem (since you can have duplicates), but I suspect you can easily adapt a combination-generation algorithm (like the traditional odometer-style algorithm: increment the last number until you get to the max, then add one to the previous and "roll over" the new number).

Note that you can make a vector that will resize itself as you go, so you can, at the beginning of the loop, push_back another number and now you've got 4 coefficients to play with instead of 3 (for instance).
Thank you very much. But the problem is not about resize a vector. It is resize the number of loops. This is difficult. Do you have some method to solve this problems?

9. Perhaps this?
Code:
```a[0]=0;
for(int i=0;i<max;++i)
for(int j=0;j<max;++j)
for(int k=1;k<max;++k)
lambda-a[i]-a[j]-a[k];```

10. Originally Posted by lijr07
Thank you very much. But the problem is not about resize a vector. It is resize the number of loops. This is difficult. Do you have some method to solve this problems?
Since there are always and forever two loops, there is no resizing the number of loops problem.

ETA: Just to be clear about where the loops start and stop: The code to generate
lambda-a[1], lambda-a[2], ..., lambda-a[k-1], (the sum of coefficients of a[i] is -1)
and to generate
lambda-2a[1], lambda-a[1]-a[2], lambda-a[1]-a[3], ..., lambda-a[1]-a[k-1], lambda-2a[2], lambda-a[2]-a[3], ..., lambda-a[2]-a[k-1], ..., lambda-a[k-2]-a[k-1], lambda-2a[k-1], (the sum of coefficients of a[i] is -2)
and to generate
lamdba-3a[1], ... (the sum of coefficients of a[i] is -3)

is exactly the same code (except for one character difference, where 1 changes to 2 changes to 3). If you are using different code for each of these (for example, extra for loops), then your code is b0rken.

11. I have an idea to solve this problem. But it is not successful. I use d[l] to record some value (the other values are obtained from d[l]). Could you help me?

Code:
```#include <stdio.h>

#define max_rank 100
#define max_length 1000

void copy(int c[max_rank], int e[max_rank], int rank) {
int i;

for (i=0;i<rank;i++) {
e[i]=c[i];
}
}
int main() {
int i, j, l, n=4, rank=4;

struct vector
{
int a[max_rank];
int i;
};
typedef struct vector vector;
vector d[max_length];
vector c;

for(i=0; i<rank; i++){
if(i==0){
c.a[i]=n;
}
else{
c.a[i]=0;

}

}

c.i=0;

l=0;

printf("c=");
for(j=0; j<rank; j++){
printf("%d, ", c.a[j]);
}
printf("\n");

while(1){

for(i=c.i; i<rank-1; i++){

if(c.a[i-1]>0 && i>0){

for(j=0; j<rank; j++){
d[l].a[j]=c.a[j];
}
d[l].i=i;
printf("d=");
for(j=0; j<rank; j++){
printf("%d, ", d[l].a[j]);
}
printf("\n");

l++;  printf("d[%d].i=%d, l=%d\n",l-1, d[l-1].i,l);
}

c.a[i]=c.a[i]-1;
c.a[i+1]=c.a[i+1]+1;
/*
if(i==rank-2 && c[rank-2] != 0){
i=rank-3;

}

*/
printf("c=");
for(j=0; j<rank; j++){
printf("%d, ", c.a[j]);
}
printf("\n");

}

for(j=0; j<rank; j++){
c.a[j]=d[l-1].a[j];
}
c.i=d[l-1].i;

l--;

if(l==-1){
break;
}

}

return 0;

}```

12. 1. Look at what you posted. Single-letter variable names, white space everywhere, inconsistent indentation. If you are actually expecting us to read this code, then please make some attempt at making it readable. (Yes, I've got auto-indenting tools, and I'll use them on your code as soon as I'm done typing, but.)

2. You have posted in the C++ forum. Are you not intending to use C++? (This is not C++ code.)

Okay, these seem like the only two lines that change your values:
Code:
```                    c.a[i]=c.a[i]-1;
c.a[i+1]=c.a[i+1]+1;```
All this appears to be doing is switching 0,1 to 1,0; it certainly isn't moving you around anywhere else. Remember your goal: you want to generate all the numbers (I'm using n=4 and k=4 since that's what you appear to have in your program)
0000,0001,0002,0003,0011,0012,0013,0022,0023,0033, 0111,0112,0113,0122, etc., in that order (or at least that seemed important to you earlier). So you need to repetitively add 1 to the last number, and when that goes over the limit "carry" that overflow back to the left as far as necessary, filling forward with the new number. It's odometer-like, if you remember odometers.

13. This is C code. I am sorry I made a mistake to put it here. But I think that C and C++ are similar. The sum of each set of numbers should be 4. But 0000, 0001, 0002, ... do not have this property. I need 4000, 3100, 3010, 3001, 2200, 2110, 2101, 2020, 2011, 2002, 1300, 1210, 1111, 1102, 1021, 1012, 1003, 0400, 0310, 0301, 0220, 0211, 0202, 0130, 0121, 0112, 0103, 0040, 0031, 0022, 0013, 0004. So I use d[l] to record some values. d is a stack.

14. No, you want 0000, 0001, 0002, etc. Perhaps to make it clearer, here would be the values for the loop when n = 3:
000, 001, 002, 003, 011, 012, 013, 022, 023, 033, 111, 112, .... Notice the numbers still go up to 3 because k=4. The first one (000) represents lambda -a[0]-a[0]-a[0] (or lambda-3a[0]); the next one represents lambda-a[0]-a[0]-a[1] (or lambda-2a[0]-a[1]); the next one represents lambda-a[0]-a[0]-a[2] (or lambda-2a[0]-a[2]), and so on.