C- integers[ARRAY]之间2个变量的组合

Question

这个程序将列出所有可能的组合，其中+和-可以放在整数之间：

假设我有3个整数:输入:4 5 6

因此，我可以将+和-符号放在4种可能的组合中:输出: 4+5+6，4-5-6，4+5-6，4-6+5

我认为这种可能的组合的公式是2到N，其中N是整数之间的空格数量。

下面是我的代码：

#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");


}

但我认为这会导致内存问题，因为为了找到唯一的组合而执行的循环数量很多。

有人能帮我吗？如何使这段代码成为可执行代码？

Answer 1

这是代码，为了理解我做了什么，你需要画一个二叉树，然后从底部开始加减值。

#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

可能性的数量是2^N，这是正确的，其中N是整数之间的槽数。

我不想纠正您的代码，也不想包含我自己的代码，因为我不知道您的特定假设(例如，每个插槽中是否可以有一个以上的空格字符；您是否可以有其他空格字符，如制表符等)。不过，以下是我将使用的整体算法：

• 遍历字符串并找到所有N个插槽(即，计算它们的数量并存储指向它们在i_1上的location).
• Loop的指针，...，i_N从0到1(这导致2^N个可能性；如果您需要在任意数量的dimensions).
• For上实现循环的帮助，请让我知道每次选择i_1，...，i_N的值时，打印字符串的修改副本，其中每个插槽中的第一个字符将由'+‘或'-’替换，具体取决于相应的值是0还是1。

这样，您不需要存储太多(只需要存储槽的位置和循环变量)；您的存储需求是O(N)。然而，仍然有大量的可能性，因此对于大N，打印它们将需要时间。此外，如果您存储这些可能性(例如，将它们保存到一个文件中)，这可能会超出您的存储容量，同样对于大N。