Thread: 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)
...

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

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

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.

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.

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?

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?

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;
 

}

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.

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.