如何使用C生成所有可能的子序列,包括字符串的非连续子序列

例如,

char str[20]; str="ABCD"; 

输出:

 1 - A, B, C,D 2 - AB,AC, AD BC, BD, CD. 3 - ABC, ABD, BCD. 4 - ABCD. 

子序列仅以从左到右的方式生成。 谢谢 :)

 #include #include  #include int sub[10]; void next(int max, int length) { int pos = length - 1,a; //find first digit that can be increased while(pos >= 0) { if(sub[pos] == max - (length - 1 - pos)) pos--; else break; } sub[pos]++; //increase digit //update other digits for( a = pos+1; a < length; a++) sub[a] = sub[a-1] + 1; } int main() { char word[100]; printf("Enter a word = "); scanf("%s",word); int max = strlen(word) - 1,n,i,a,b; for(n=1; n <= max+1; n++) { printf("\n"); for(i = 0; i < n; i++) { sub[i] = i; } for(a = 0; ; a++) { for(b=0; b < max+1; b++) printf("%c",word[sub[b]]); printf("\n"); if(sub[0] == max - (n - 1)) break; else next(max, n); } printf("\n"); } return 0; } 

此代码仅生成长度等于字符串长度的子序列 ,并且它还重复特定字符。

不是最干净,最有效的代码,但这样做:D

 #include  #include  #include  #include  char *printForMask(int mask, char *str) { int i = 0; int j = 0; char *maskedString = (char *)malloc(sizeof(char) * strlen(str) + 1); for (; mask > 0; mask >>= 1, j++) { if (mask & 1) maskedString[i++] = str[j]; } maskedString[i] = '\0'; return maskedString; } int main() { char str[20] = "ABCD"; int mask = 1; int maskLen = 1; int stringLen = strlen(str); for (maskLen = 1; maskLen <= stringLen; maskLen++) { printf("%d ", maskLen); for (mask = (int)pow(2,maskLen) - 1; mask <= (int) pow(2, stringLen) - 1; mask <<= 1) { char *temp = printForMask(mask, str); printf ("%s%s", temp, (mask << 1 <= (int) pow(2, stringLen) - 1) ? ", " : "\n"); free(temp); } } return 0; } 

编辑

对于字符串ABCD

 str[0] = 'A' str[1] = 'B' str[2] = 'C' str[3] = 'D' 

对?

所以我正在做的是使用整数2^strlen(str) - 1的二进制表示,在这种情况下将是2^4 - 1 = 15 = 0b1111在主函数的第一个for循环中,我增加掩码,意味着从mask = 0b0001 ,对于循环的每次迭代,将掩码增加到mask = 0b1111并且在内部for循环中,我移动掩码以便发生类似这样的事情

 mask = 0b0001 //A mask = 0b0010 //B mask = 0b0100 //C mask = 0b1000 //D //The inner loop will finish here, and the mask length will become 2 mask = 0b0011 //AB mask = 0b0110 //BC mask = 0b1100 //CD //etc. The string representation is made by the function printForMask()