Solved

print any sequence length

Posted on 2006-11-05
8
209 Views
Last Modified: 2010-04-15
hi, I have a program that can print 3 sequence of length from a matrix (like below). It print all possible combination for sequence length of 3 (which is 3^3=27 possible combinations).
how can I modify the code to let me print any sequence length. I have try to use multiple for loop. it works, but if I want to have sequence of 100, I need write 100 for loops..........terrible!!!

how can I do it more efficiently?

----------------my code-------------------------
#include <stdio.h>
#include <float.h>

 
int matrix [3][3]={{3,3,4},
                     {8,1,1},
                     {3,3,4}};                    
                   

main (){
    int i,j,k,l;
    long max = 0;

     for (i=0; i<3; i++){
          printf("\n");
         for (j=0; j<3; j++) {
             //printf("\n");
            for (k=0; k<3; k++){
                   printf("Prob(%d%d%d)=%d\n",i,j,k,matrix[i][j]+matrix[j][k]);  
                 
              }//end third for
                       
        }// end second for
    }// end first for

    system("pause");
}
0
Comment
Question by:rmtogether
  • 3
  • 3
  • 2
8 Comments
 
LVL 13

Assisted Solution

by:marchent
marchent earned 100 total points
ID: 17877135
/**
  @author marchent
*/

#include<stdio.h>
#define LEN 4  //change the value of LEN for different size

int matrix[LEN][LEN]={{1,2,3,4},
                     {1,2,3,4},
                     {1,2,3,4},
                     {1,2,3,4}};
int index[LEN];  //initially 0
int output[LEN];

void print_output()
{
    for(int i=0;i<LEN;i++)
        printf("%d ",output[i]);
    printf("\n");
}
/**
  generating combination using backtracking
*/
void generate_combination(int count)
{
    if(count < LEN)
        for(int i=index[count];i<LEN;i++)
        {
            output[count] = matrix[count][index[count]];
            //call recursively
            generate_combination(count+1);
            if(count == LEN-1)//a combination found
                print_output();
            index[count]++;
            //set index[count] for another combination
            if(index[count] >= LEN) index[count] = 0;
        }
}

int main()
{
    generate_combination(0);
    return 0;
}

~marchent~
0
 
LVL 13

Expert Comment

by:marchent
ID: 17877140
heeeewwoooooofff
0
 
LVL 13

Expert Comment

by:marchent
ID: 17877151
mind that, it will work maximum for LEN = 7 i guess. cause 7^7 is already a large number for recursion. and for 100!!! no way u can't 100^100 = how many combinations ?

~marchent~
0
Three Reasons Why Backup is Strategic

Backup is strategic to your business because your data is strategic to your business. Without backup, your business will fail. This white paper explains why it is vital for you to design and immediately execute a backup strategy to protect 100 percent of your data.

 

Author Comment

by:rmtogether
ID: 17877582
hi, thanks
but i only get 1 1 1 1 for the output.

my original code return me from 000 to 222 (3^3=27 results), output like below:

Prob(000)=6
Prob(001)=6
Prob(002)=7
Prob(010)=11
Prob(011)=4
Prob(012)=4
Prob(020)=7
Prob(021)=7
Prob(022)=8

Prob(100)=11
Prob(101)=11
Prob(102)=12
Prob(110)=9
Prob(111)=2
Prob(112)=2
Prob(120)=4
Prob(121)=4
Prob(122)=5

Prob(200)=6
Prob(201)=6
Prob(202)=7
Prob(210)=11
Prob(211)=4
Prob(212)=4
Prob(220)=7
Prob(221)=7
Prob(222)=8

I would like to expand my program to do 3^n sequence
for example,  if n=10, the result should return  3^10 results, which is from 0000000000 to 5555555555.
0
 
LVL 84

Expert Comment

by:ozo
ID: 17879223
#include<stdio.h>
#define LEN 5  //change the value of LEN for different size

int matrix[LEN][LEN];
int INDEX[LEN+1];  //initially 0
int output[LEN];

void print_output()
{
  int i;
  for(i=0;i<=LEN;i++){
        printf("%d",INDEX[i]);
  }
  int sum=0;  
  for( i=0;i<LEN;i++ ){
    sum += matrix[INDEX[i]][INDEX[i+1]];
  }
  printf("=%d\n",sum);
}
/**
  generating combination using backtracking
*/
void generate_combination(int count)
{
  int i;
  if( count > LEN ){
    print_output();
    return;
  }
  for(i=0;i<LEN;i++ ){
    INDEX[count]=i;
    generate_combination(count+1);
  }
}

int main()
{
  int i,j;
  for( i=0;i<LEN; i++ ){
     for(j=0;j<LEN;j++){
       printf("%d ",matrix[i][j] = rand()%LEN);
     }
     printf("\n");
  }
  generate_combination(0);
}
0
 

Author Comment

by:rmtogether
ID: 17883213
hi, oze
thank you very much.

my matrix is pre define. it is not necessary random generate at this point. I modify your code below, there is something I don't understand...

I test LEN=3, which return me correct combination  paths with correct answer

but for others,
like LEN=2, which should return me 27 paths, but the code only return me 8 paths

for any LEN above 3, they return correct combination paths, but the sum values seems not correct. for example, if LEN=5, there aresome negative sum values

I try to find this error by myseflt, but still can't. could you please help me about this


-----------------code--------------------------------------------------------------------

 #include<stdio.h>
#define LEN 4  //change the value of LEN for different size

//int matrix[LEN][LEN];
int INDEX[LEN+1];  //initially 0
int output[LEN];

int matrix [3][3]=  {{3,3,4},
                     {8,1,1},
                     {3,3,4}};  


void print_output()
{
  int i;
  for(i=0;i<=LEN;i++){
        printf("%d",INDEX[i]);
  }
  int sum=0;  
  for( i=0;i<LEN;i++ ){
    sum += matrix[INDEX[i]][INDEX[i+1]];
  }
  printf("=%d\n",sum);
}
/**
  generating combination using backtracking
*/
void generate_combination(int count)
{
  int i;
  if( count > LEN ){
    print_output();
    return;
  }
  for(i=0;i<LEN;i++ ){
    INDEX[count]=i;
    generate_combination(count+1);
  }
}

int main()
{
  int i,j;
  /*
  for( i=0;i<LEN; i++ ){
     for(j=0;j<LEN;j++){
       printf("%d ",matrix[i][j] = rand()%LEN);
     }
     printf("\n");
  }
  */
  generate_combination(0);
  system("pause");
}
0
 
LVL 84

Accepted Solution

by:
ozo earned 400 total points
ID: 17883729
#include<stdio.h>
#define LEN 4  //change the value of LEN for different size

//int matrix[LEN][LEN];
int INDEX[LEN+1];  //initially 0
int output[LEN];

int matrix [3][3]=  {{3,3,4},
                     {8,1,1},
                     {3,3,4}};  


void print_output()
{
  int i;
  for(i=0;i<=LEN;i++){
        printf("%d",INDEX[i]);
  }
  int sum=0;  
  for( i=0;i<LEN;i++ ){
    sum += matrix[INDEX[i]][INDEX[i+1]];
  }
  printf("=%d\n",sum);
}
/**
  generating combination using backtracking
*/
void generate_combination(int count)
{
  int i;
  if( count > LEN ){
    print_output();
    return;
  }
  for(i=0;i<3;i++ ){
    INDEX[count]=i;
    generate_combination(count+1);
  }
}

int main()
{
  int i,j;
  /*
  for( i=0;i<LEN; i++ ){
     for(j=0;j<LEN;j++){
       printf("%d ",matrix[i][j] = rand()%LEN);
     }
     printf("\n");
  }
  */
  generate_combination(0);
  system("pause");
}
0
 

Author Comment

by:rmtogether
ID: 17883998
hi, ozo
thank you very much!!  this is exactly what I want.

by the way, I may improve this program later. If I have any question, how can I contact you?


0

Featured Post

Master Your Team's Linux and Cloud Stack

Come see why top tech companies like Mailchimp and Media Temple use Linux Academy to build their employee training programs.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Problem with MFCApp 78 383
Compile VxWorks Toronado project under Visual Studio 11 198
Inorder binary search tree 5 164
How to build c program using make in mingw environment? 9 61
Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and inf…
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.

770 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question