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

1. 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. 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!

3. 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. 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. Originally Posted by cfan
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.

6. 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. or is "the" a substring of "beach towel" since all the letters are there somewhere?

yes

8. each combination of chars in every length

9. 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. 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. 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.

12. Originally Posted by quzah
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. Interesting that a professional developer hasn't learned what the unsigned keyword is used for.

14. So apparently "professional" means "there are extra spaces in the output for no good reason." Professionalism is easier to obtain than I thought!

15. Originally Posted by tabstop
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.