C - Combination of 2 Variables between integers[ARRAY]

Question

This program will list down all the possible combinations where + and - can be placed between integers:

Suppose I have 3 integers: INPUT: 4 5 6

so, there are [4] possible combinations that I can put + and - sign: which is: OUTPUT: 4+5+6, 4-5-6, 4+5-6, 4-6+5

I think the formula of this possible combinations are 2 to the N where N is the number of spaces between integers.

Here's my code:

#include<stdio.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int main(){
    int i,j,sign,space=0,z=0,x=0,y=0,count=0,a=0,d,
    flag=0,combi,m,n;
    srand((unsigned) time(NULL));
    char string[100][100],c,hold[100][100],fin[x][y];

    char num[100]="1 2 3";

    for(i=0;i<strlen(num);i++){
        if(isspace(num[i]))
        space++;
    }
    combi=pow(2,space);

    for(i=0;i<combi;i++){
        strcpy(string[i],num);
    }
    for(i=0;i<combi;i++){
        printf("%d: [%s]\n",i+1,string[i]);
    }

//    strcpy(hold,string);

    for(x=0;x<combi;x++){
//        check:

        for(y=0;y<strlen(string);y++){
            if(isspace(string[x][y])){
                sign=rand()%2;
                if(sign==0){
                    c='+';
                }else{
                    c='-';
                }
                string[x][y]=c;
            }
        }
        strcpy(hold[z],string[x]);
        z++;
        if(a==0){
            strcpy(hold[z],string[x]);
//            printf("[%d]",z);
            z++;
            a++;
        }
        else{
            check:
            for(d=0;d<z;d++){
            check:
                if(strcmp(hold[d],string[x])!=0){
                    flag++;
                }
                else if(strcmp(hold[d],string[x])==0){
                     for(y=0;y<strlen(string[x]);y++){
                        if((string[x][y])==','||(string[x][y])=='_'){
                            sign=rand()%2;
                            if(sign==0){
                                c='+';
                            }else{
                                c='-';
                            }
                            string[x][y]=c;
                        }
                    }
                    goto check;
                }

                ///
                ///
                if(flag==z){
                    strcpy(hold[z],string[x]);
                    z++;
                    a++;
                    flag=0;
                }
            }
        }

    }
    printf("\n\n");
    for(i=0;i<combi;i++){
        printf("%d: %s\n",i+1,hold[i]);
    }
    printf("\n\n");


}

But it will result to memory problems I think due to the number of loops execute to find a unique combination.

Can someone help me? How to make this code executable?

Answer 1

This is the code , to understand what I did you need to draw a binary tree and start adding and subtracting values from the bottom .

#include <stdio.h>
#include <stdlib.h>

// mul is pow for ints ... just use (int)pow(x,y) and include <math.h> 

int mul(int a , int x ) {
  int i ;
  int val = 1 ; 
  for(i=0 ; i< x ; i++) {
    val *= a ; 
  }
  return val ; 
}

void sum(int *arr , int n , int* res) {

int * tmp = malloc(mul(2,n)*sizeof(int)) ;
int tmpSize = mul(2,n) ; 

if(!tmp) {
  printf("Your input size is to large") ;
  return ;
}

tmp[0] = arr[0] + arr[1] ; 
tmp[1] = arr[0] - arr[1] ; 

int i , j , p=0 , k=2 ;
for( i=2 ; i< n ; i++ ){
  for ( j=0 ; j<mul(2,i-1) ; j++ ) {

    tmp[k] = tmp[p+j] + arr[i] ; 
    tmp[k+1] = tmp[p+j] - arr[i] ; 
    k += 2 ; 
  }
  p= mul(2,i+1) - mul(2,i) - 2 ;
}

 int index = mul(2,n) - mul(2,n-1) - 2 ; 
 for( i=0 ; i<mul(2,n-1); i++ ) {
   res[i] = tmp[index+i] ;
 }

}

int main(void) {

 int a[4] = { 3,2,6,8 } ;  
 int res[16] = {0} ; 
 sum(a,4,res) ; 
 int i ;
 for (i=0 ;i<8 ; i++) {
   printf("%d\n",res[i]) ;
 }

 return 0;
}

Answer 2

You are correct that the number of possibilities is 2^N, where N is how many slots between the integers you have.

I'm not trying to correct your code, or include my own code, because I don't know your specific assumptions (e.g., can there be more than one space character in each slot; can you have other whitespace characters, like tabs, etc.). Still, here's the overall algorithm I would use:

• Loop over the string and find all N slots (i.e., compute their number and store pointers to their location).
• Loop over i_1, ..., i_N from 0 to 1 (this results in the 2^N possibilities; let me know if you need help implementing a loop over an arbitrary number of dimensions).
• For each selection of values for i_1, ..., i_N, print a modified copy of the string where the first character in each slot is replaced by '+' or '-' depending on whether the corresponding value is 0 or 1.

This way, you don't need to store much (just the location of the slots, and the loop variables); your storage requirements are O(N). However, there's still going to be plenty of possibilities, so it will take time to print them all out for large N. Moreover, if you store the possibilities (e.g., saving them into a file), this will likely exceed your storage capacity, again for large N.