Thread: the easyiest way of finding all the combinations of a string..

  1. #1
    Banned
    Join Date
    Jul 2009
    Posts
    46

    the easyiest way of finding all the combinations of a string..

    i have a recursive subset code
    but its way too long to remember

    is there some easier iterative algorithm to generate all the sub string of a given string

    ?

  2. #2
    Making mistakes
    Join Date
    Dec 2008
    Posts
    476
    Looks like homework, but any recursive program can be rewritten with a loop. Why the heck do you want to remember your prog? Simply write it down!
    Last edited by Brafil; 08-02-2009 at 11:49 AM.

  3. #3
    Banned
    Join Date
    Jul 2009
    Posts
    46
    the problem is that i have the code of recursive subsets
    but i dont andestand it at all.

    could you tell me the general iterative index way of generating each string.

  4. #4
    Banned
    Join Date
    Jul 2009
    Posts
    46
    i dont want you to solve it for me.
    i want to understand the general way
    how to play whic a string in order to get every combination
    in iterative way
    ??

  5. #5
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by cfan View Post
    i dont want you to solve it for me.
    i want to understand the general way
    Sometimes programming is about finding the right algorithm and implementing it, other times it is about coming up with an algorithm yourself. If you do not like this "recursive subset code" and want an alternative, try and see what you can come up with. If you have trouble implementing it -- for example, if it means you need to pass parameters in an unfamiliar way, etc, you can always ask specific questions about that.

    Use a simple string for a test case where you already know the proper answer, this makes it easier to tell if the idea works and if not how it might be made to work.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Another person with this mystical "recursive subset" code. By "substring" do you mean the typical meaning of the word "substring" (which really wouldn't require recursion so far as I can tell) or is "the" a substring of "beach towel" since all the letters are there somewhere?

  7. #7
    Banned
    Join Date
    Jul 2009
    Posts
    46
    or is "the" a substring of "beach towel" since all the letters are there somewhere?

    yes

  8. #8
    Banned
    Join Date
    Jul 2009
    Posts
    46
    each combination of chars in every length

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    So you nearly said the magic word and won a hundred dollars: you said the word combination, but what you're actually after is all the permutations of your string. The algorithm for generating permutations in order requires something like four steps; it's just about any textbook on algorithms or discrete math and I just found it on Wikipedia in the "permutation" article.

  10. #10
    Registered User
    Join Date
    Dec 2010
    Posts
    1
    Although this is an old post it still comes up in search engines. So, given the horrid advice on this topic I thought I'd demonstrate how a professional developer solves the problem; not an academic or hobbiest. This is easiest solved by not thinking statistics - it's a n choose 2 problem which should ring "binary" to everyone.

    For shipping code you'd want to use __int64 or whatever datatype contains your largest possible. Since 64 bits (e.g. 64 items) gives you 18 quintillion combinations it should more than fill most needs. Breaking this up to efficiently use multi-hyperthreads (think i7 here) or extend beyond native 64-bit fields left to the reader.

    Syntax formatted for easy viewing and error handling left out >>

    Code:
    void PrintCombinations( LPCWSTR pcwszBuffer, int nLength )
    {
        int nTotalCombinations;
        int nCharIndex;
    
        nTotalCombinations = 1;
        nTotalCombinations = nTotalCombinations << nLength;
    
        for( int iIndex = 1; iIndex < nTotalCombinations; iIndex++ )
        {
            nCharIndex = 0;
            for( int nCombination = iIndex; nCombination > 0; nCombination = nCombination >> 1, nCharIndex++ )
            {
                if( nCombination&0x00000001 )
                {
                    wprintf( L"%c", pcwszBuffer[nCharIndex] );
                }
                else
                {
                    wprintf( L" " );
                }
            }
            wprintf( L"\n" );
        }
        wprintf( L"\nCombinations: %d\n\n", nTotalCombinations-1 );
    }
    
    int _tmain(int argc, _TCHAR* argv[])
    {
        WCHAR wszBuffer[] = L"ABCD";
    
        PrintCombinations( wszBuffer, lstrlen(wszBuffer) );
    
        wprintf( L"Any key exits...\n" );
        _getch();
        return 0;
    }
    OUTPUT (which is column aligned with fixed-width fonts)
    A
    B
    AB
    C
    A C
    BC
    ABC
    D
    A D
    B D
    AB D
    CD
    A CD
    BCD
    ABCD

    Combinations: 15

    Any key exits...

  11. #11
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Good job! You made a new account to post in a year old thread! All you needed to do was visit Wikipedia, but hey, good job anyway!


    Quzah.
    Hope is the first step on the road to disappointment.

  12. #12
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by quzah View Post
    Good job! You made a new account to post in a year old thread! All you needed to do was visit Wikipedia, but hey, good job anyway!


    Quzah.
    Oh I dunno, I'm thinking he just wanted to brag about how professional he is while hinting (in a not entirely subtle way) that we're all just a bunch of amateurs.

  13. #13
    Registered User
    Join Date
    Mar 2009
    Posts
    344
    Interesting that a professional developer hasn't learned what the unsigned keyword is used for.

  14. #14
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    So apparently "professional" means "there are extra spaces in the output for no good reason." Professionalism is easier to obtain than I thought!

  15. #15
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    733
    Quote Originally Posted by tabstop View Post
    So apparently "professional" means "there are extra spaces in the output for no good reason." Professionalism is easier to obtain than I thought!
    He is just p r o f e s s i o n a l.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. RicBot
    By John_ in forum C++ Programming
    Replies: 8
    Last Post: 06-13-2006, 06:52 PM
  2. Calculator + LinkedList
    By maro009 in forum C++ Programming
    Replies: 20
    Last Post: 05-17-2005, 12:56 PM
  3. problems with overloaded '+' again
    By Brain Cell in forum C++ Programming
    Replies: 9
    Last Post: 04-14-2005, 05:13 PM
  4. Linked List Help
    By CJ7Mudrover in forum C Programming
    Replies: 9
    Last Post: 03-10-2004, 10:33 PM
  5. Warnings, warnings, warnings?
    By spentdome in forum C Programming
    Replies: 25
    Last Post: 05-27-2002, 06:49 PM