c - 如何使用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<stdio.h>
#include <conio.h>
#include<string.h>


 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 <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

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
在main函数的第一个for循环中，我增加了mask
从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()

关于c - 如何使用C生成字符串的所有可能子序列，包括字符串的非连续子序列，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14561014/