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
?
This is a discussion on the easyiest way of finding all the combinations of a string.. within the C Programming forums, part of the General Programming Boards category; i have a recursive subset code but its way too long to remember is there some easier iterative algorithm to ...
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
?
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 12:49 PM.
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.
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
??
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
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?
or is "the" a substring of "beach towel" since all the letters are there somewhere?
yes
each combination of chars in every length
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.
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 >>
OUTPUT (which is column aligned with fixed-width fonts)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; }
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...
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.
Interesting that a professional developer hasn't learned what the unsigned keyword is used for.
So apparently "professional" means "there are extra spaces in the output for no good reason." Professionalism is easier to obtain than I thought!