Thread: Generate all subsequence combinations

  1. #1
    Registered User
    Join Date
    Oct 2010
    Posts
    11

    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?

  2. #2
    Registered User
    Join Date
    Jun 2011
    Posts
    4,513
    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.

  3. #3
    Registered User
    Join Date
    Oct 2006
    Posts
    3,445
    C++ has no "yield" functionality, in the language or standard library. You'll probably just need to fill a container, return it, and then iterate over it. Fortunately, C++ now has range-based for loops, so your "generator" function can return a vector, map, or some other such container, and you can just iterate over the result.

    Furthermore, I'm not sure C++ is the right tool for the job, since the return type of your function is dynamic.
    What can this strange device be?
    When I touch it, it gives forth a sound
    It's got wires that vibrate and give music
    What can this thing be that I found?

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,419
    Quote Originally Posted by Freaky256
    But have some serious trouble to rewrite the 'yield' in C++.
    Does anyone know how to do this?
    Other concerns aside, you could investigate Boost.Coroutine, though I cannot comment further on the library as I have never tried it.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    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;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Subsequence robot(player) playings.
    By Romyo2 in forum C Programming
    Replies: 8
    Last Post: 05-04-2015, 01:58 AM
  2. Max SubSequence using recursion
    By Amoxaphobic in forum C++ Programming
    Replies: 4
    Last Post: 11-10-2011, 02:46 PM
  3. finding the largest ascending subsequence..
    By transgalactic2 in forum C Programming
    Replies: 92
    Last Post: 01-21-2009, 08:57 AM
  4. Minimum Positive Subsequence Sum
    By CrazyNorman in forum C++ Programming
    Replies: 2
    Last Post: 09-11-2008, 04:25 AM
  5. Longest Common Subsequence
    By stimpyzu in forum Tech Board
    Replies: 4
    Last Post: 04-04-2005, 03:18 PM