Thread: Generate all subsequence combinations

I need all combinations of subsets of a string. In addition, a subset of length 1 can only be followed by a subset with length > 1. E.g. for string 4824 the result should be:

[ [4, 824], [4, 82, 4], [48, 24], [482, 4], [4824] ]

I have the python code to this solution so far:

Code:

	def getSubSequences(self, s, minLength=1):
	    if len(s) >= minLength:
		for i in range(minLength, len(s) + 1):
		    for p in self.getSubSequences(s[i:], 1 if i > 1 else 2):
		        yield [s[:i]] + p
	    elif not s:
		yield []

But have some serious trouble to rewrite the 'yield' in C++.
Does anyone know how to do this?

Cross-posted:
Transform python yield into c++ - Stack Overflow
Generate all subsequence combinations - C++ Forum

Try posting your best attempt, and you might receive better advice.

Ha, I saw this topic and laughed because I've been stumped by this very same problem. Interestingly enough, this board has solved it for me in the past so I dug up the solution that I liked the most (not that I didn't appreciate all those who helped).

Let's think for a second about what we're dong. We're doing string splitting here. What is string splitting fundamentally? It's taking indices of an array of chars and treating those to be the "split" points. That's interesting.

For any given index, we're either going to split the string there or not. In binary, this might look like :

Code:

0110

To get literally every substring, we just iterate, one value at a time.

For a 4 character string we have only 3 split points. Imagine the value 0123. At the most we can only split it like this 0 | 1 | 2 | 3. As you can see, we can only split this string in 3 places. This means that our substrings look like this :

Code:

000 // 0 
001 // 1
010 // 2
011 // 3
100 // 4
101 // 5
110 // 6
111 // 7

So combo 0 is where we don't split anything, combo 1 is where we split at the first possible, combo 3 is where we split at the first and second locations and 7 is where we split at all 3.

The code basically looks like this :

Code:

// gcc -Wall -Wextra -pedantic -O3 -std=c11 -o solution solution.c

#include <stdio.h>
#include <string.h>
 
void printcombo(const char *s, int mask)
{
        int i;
 
        for (i = 0; s[i] != '\0'; i++) {
                putchar(s[i]);
                if (mask & 1 << i)
                        printf(", ");
        }
}
 
int main(void)
{
        const char s[] = "4824";
        int i, n;


        // here n is the total number of split locations
        n = 1 << (strlen(s) - 1);
        for (i = 0; i < n; i++) {
                printcombo(s, i);
                putchar('\n');
        }
        return 0;
}