• C

# print any sequence length

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");
}
###### Who is Participating?

Commented:
#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

Commented:
/**
@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

Commented:
heeeewwoooooofff
0

Commented:
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 Commented:
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

Commented:
#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 Commented:
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

-----------------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

Author Commented:
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
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.