Solved

print any sequence length

Posted on 2006-11-05
8
207 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
 

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
How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

 
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

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

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…
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.

760 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

Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!

Get 1:1 Help Now