428,742 Members | 1,570 Online
Need help? Post your question and get tips & solutions from a community of 428,742 IT Pros & Developers. It's quick & easy.

# Combinations in C?

 P: n/a Hello all, I have an array of values which I would like to generate all possible combinations for. And example would be the values "a,b,c". This would produce the following: a ab abc ac b bc c Does anybody know of the algorithm to produce this? I've seen the topic discussed, but never for strings or anything of the such. Most discussion is regarding calculating the number of combinations...which I don't care about. -- Tom Cameron tomdrdabblesus http://drdabbles.us Nov 14 '05 #1
19 Replies

 P: n/a Thomas Cameron wrote: Hello all, I have an array of values which I would like to generate all possible combinations for. And example would be the values "a,b,c". This would produce the following: a ab abc ac b bc c Does anybody know of the algorithm to produce this? I've seen the topic discussed, but never for strings or anything of the such. Most discussion is regarding calculating the number of combinations...which I don't care about. Hint #1: In any combination, each of a,b,c is either "in" or "out." Does that suggest anything? Hint #2: One combination is missing from your list. Does the nature of the missing combination make Hint #1 any clearer? ... and since there's an odor of homework about your question, hints are all I'm willing to provide just now. Good luck! -- Er*********@sun.com Nov 14 '05 #2

 P: n/a On Mon, 04 Apr 2005 10:17:26 -0400, Eric Sosman wrote: ... and since there's an odor of homework about yourquestion, hints are all I'm willing to provide just now. What about PERMUTATIONS ? abc acb bac bca cab aba String of lenght n makes n! permutations. What's the best algorithm ? What's the asintotic computational complexity ? What's about off-topics ? :-) (This is a real "problem" of mine: I'd like to mix up my Name-Surname string to look for significant nicknames... :-) Nov 14 '05 #3

 P: n/a On Mon, 04 Apr 2005 16:30:53 +0200, Bob wrote: abcacbbacbcacababa Find the mistake ! Nov 14 '05 #4

 P: n/a In article , Eric Sosman wrote: a ab abc ac b bc c Hint #2: One combination is missing from your list. How can you tell? -- Richard Nov 14 '05 #5

 P: n/a Also worth note is the actual answer: c b b c a a c a b a b c This is directly from the PERL that I found. Where did I miss one, unless you're referring to the empty set...which I DO want, but can add manually if need be. -- Tom Cameron tomdrdabblesus http://drdabbles.us Nov 14 '05 #7

 P: n/a Thomas Cameron wrote: Also worth note is the actual answer: c b b c a a c a b a b c This is directly from the PERL that I found. Where did I miss one, unless you're referring to the empty set...which I DO want, but can add manually if need be. Hint #3 You have three "positions" to switch on or off (2 choices) which yields 2**3 possibilities... Something ringing? Cheers Michael -- E-Mail: Mine is an /at/ gmx /dot/ de address. Nov 14 '05 #9

 P: n/a Michael Mair wrote: Thomas Cameron wrote: Also worth note is the actual answer: c b b c a a c a b a b c This is directly from the PERL that I found. Where did I miss one, unless you're referring to the empty set...which I DO want, but can add manually if need be. Hint #3 You have three "positions" to switch on or off (2 choices) which yields 2**3 possibilities... Something ringing? Cheers Michael -- E-Mail: Mine is an /at/ gmx /dot/ de address. In reality, I have 2^19=524288 possible combinations. Of course, each element is not actually one letter, but an entire string unto itself. I assume the simplest way to do this would be to put each element into an array position and iterate through that way? Either way, this is going to be a pain in the backside, I can tell. And no, nothing's ringing a bell yet...as I'm a novice with C (at best). -- Tom Cameron tomdrdabblesus http://drdabbles.us Nov 14 '05 #10

 P: n/a Thomas Cameron wrote: Also worth note is the actual answer: c b b c a a c a b a b c This is directly from the PERL that I found. Where did I miss one, unless you're referring to the empty set...which I DO want, but can add manually if need be. Yes, the empty combination was the missing one. Since your followups seem less like homework than the original post, I'll offer an answer. In each combination, as I wrote earlier, each of a,b,c is either "in" or "out." The "in-ness" or "out-ness" of any particular letter can be specified by one bit -- let's say zero means "out" and one means "in." Now pick one bit for each letter, say a=4, b=2, c=1, and then count from zero to seven in binary: 0: _ _ _ 1: _ _ c 2: _ b _ 3: _ b c 4: a _ _ 5: a _ c 6: a b _ 7: a b c An easy way to do this in a program is to use a loop to count a value from zero through seven. For each value, use an inner loop to inspect each of the 1,2,4 bits and output the corresponding letter if the bit is set. Generalizing to N objects where N does not exceed the number of bits in an `unsigned long' is straightforward. Generalizing to larger N is a bit harder -- but you wouldn't want the output anyhow. ... -- Er*********@sun.com Nov 14 '05 #11

 P: n/a Eric Sosman wrote: Yes, the empty combination was the missing one. Since your followups seem less like homework than the original post, I'll offer an answer. In each combination, as I wrote earlier, each of a,b,c is either "in" or "out." The "in-ness" or "out-ness" of any particular letter can be specified by one bit -- let's say zero means "out" and one means "in." Now pick one bit for each letter, say a=4, b=2, c=1, and then count from zero to seven in binary: [snip] An easy way to do this in a program is to use a loop to count a value from zero through seven. For each value, use an inner loop to inspect each of the 1,2,4 bits and output the corresponding letter if the bit is set. Generalizing to N objects where N does not exceed the number of bits in an `unsigned long' is straightforward. Generalizing to larger N is a bit harder -- but you wouldn't want the output anyhow. ... -- Er*********@sun.com Lovely. This is going to be gross. So, basically, I have to keep things under 32 bits while using native 32 bit types...and honestly, the number of combinations I get from 19 is over 500,000...so 32 will kill me. I can see a need arising in the future, however, for someone (with a faster system) to generate even more than 32 combinations. I have build arrays with many more than 32 elements, and that's where I see this going eventually. I assume there's another (recursive) way to approach this problem, right? Something like: Function: for every element in the array, return that element and results of "Function". Is there a simpler way to express this? -- Tom Cameron tomdrdabblesus http://drdabbles.us Nov 14 '05 #12

 P: n/a Thomas Cameron wrote: Not necessary; simply posting is fine. Eric Sosman wrote: Generalizing to N objects where N does not exceed thenumber of bits in an `unsigned long' is straightforward.Generalizing to larger N is a bit harder -- but you wouldn'twant the output anyhow. ... Lovely. This is going to be gross. So, basically, I have to keep things under 32 bits while using native 32 bit types...and honestly, the number of combinations I get from 19 is over 500,000...so 32 will kill me. There are two possible answers to this. First, if you want to generate all combinations of 500000 objects, then yes: it will kill you. If you generate one billion such combinations every nanosecond, it will take some 3e150489 years to complete the task, by which time you may have lost interest in the outcome. The more likely answer is that you have misunderstood the construction altogether. Go back and look again: it's one bit per *object*, not one per combination. -- Er*********@sun.com Nov 14 '05 #13

 P: n/a On Mon, 04 Apr 2005 10:17:26 -0400, Eric Sosman wrote: Thomas Cameron wrote: Hello all, I have an array of values which I would like to generate all possible combinations for. And example would be the values "a,b,c". This would produce the following: a ab abc ac b bc c Does anybody know of the algorithm to produce this? I've seen the topic discussed, but never for strings or anything of the such. Most discussion is regarding calculating the number of combinations...which I don't care about. Hint #1: In any combination, each of a,b,c is either"in" or "out." Does that suggest anything? Hint #2: One combination is missing from your list.Does the nature of the missing combination make Hint #1any clearer? No, it's there, though I'm not sure whether it's the line before "a" or the line after "c". ... and since there's an odor of homework about yourquestion, hints are all I'm willing to provide just now.Good luck! -- Al Balmer Balmer Consulting re************************@att.net Nov 14 '05 #14

 P: n/a Eric Sosman wrote in news:d2**********@news1brm.Central.Sun.COM: Thomas Cameron wrote: Not necessary; simply posting is fine. In fact, please do not email me. Eric Sosman wrote: Generalizing to N objects where N does not exceed thenumber of bits in an `unsigned long' is straightforward.Generalizing to larger N is a bit harder -- but you wouldn'twant the output anyhow. ... Lovely. This is going to be gross. So, basically, I have to keep things under 32 bits while using native 32 bit types...and honestly, the number of combinations I get from 19 is over 500,000...so 32 will kill me. There are two possible answers to this. First, if you want to generate all combinations of 500000 objects, then yes: it will kill you. If you generate one billion such combinations every nanosecond, it will take some 3e150489 years to complete the task, by which time you may have lost interest in the outcome. The more likely answer is that you have misunderstood the construction altogether. Go back and look again: it's one bit per *object*, not one per combination. I am a little confused about something here. The OP stated that he is testing options to a program. 1. Why do you have to store all combinations? Generate one, throw it away, and generate another one (using a well-defined, stable algorithm). 2. Aren't there some combinations of options which just do not make any sense, and hence should not be tested? 3. Why are there so many options? Yes, I know I get a bazillion options if I type, say, man gcc, but then a lot of the options are completely independent of each other. Sinan -- A. Sinan Unur <1u**@llenroc.ude.invalid> (reverse each component and remove .invalid for email address) Nov 14 '05 #15

 P: n/a Thomas Cameron wrote: Michael Mair wrote:Thomas Cameron wrote:Also worth note is the actual answer:cbb caa ca ba b cThis is directly from the PERL that I found. Where did I miss one, unlessyou're referring to the empty set...which I DO want, but can add manuallyif need be.Hint #3You have three "positions" to switch on or off (2 choices) which yields2**3 possibilities... Something ringing?Cheers Michael--E-Mail: Mine is an /at/ gmx /dot/ de address. In reality, I have 2^19=524288 possible combinations. Of course, each element is not actually one letter, but an entire string unto itself. I assume the simplest way to do this would be to put each element into an array position and iterate through that way? Either way, this is going to be a pain in the backside, I can tell. And no, nothing's ringing a bell yet...as I'm a novice with C (at best). See Eric Sosman's explanations; FWIW, here is something to play with -- maybe it helps you to understand the idea: Note that I did not sort the whole thing the way you suggested; however, it is possible. Cheers Michael #include #include #include int main (int argc, char **argv) { unsigned long combcount, testobj; /* Handle "no object" case; could also output "\n" */ if (argc <= 1) { printf("Usage: %s object1 ... objectN\n", argc ? argv[0] : ""); exit(EXIT_SUCCESS); } /* "Throw away" argv[0] and check whether number of objects ** is within the representable range */ argc--; argv++; if (argc > sizeof combcount * CHAR_BIT) { fprintf(stderr, "Too many objects\n"); exit(EXIT_FAILURE); } /* Set combcount to "argc lowest bits set"+1, modulo for ** argc=="number of bits in unsigned long" */ combcount = 1UL << (argc % (sizeof combcount * CHAR_BIT)); do { combcount--; for (testobj=0; testobj

 P: n/a Thomas Cameron wrote: No need to mail me... [on generating combinations] I assume there's another (recursive) way to approach this problem, right? Right. Here is one: void comb(char *stack, const char *list) { if (*list == '\0') { puts(stack); } else { comb(stack, list+1); push(stack, *list); comb(stack, list+1); pop(stack); } } The stack is initially empty and needs enough capacity to accomodate all elements of the list. Generalising this from arrays of char to arrays (or other kinds of lists) of arbitrary type should be straightforward. Gergo -- The glances over cocktails That seemed to be so sweet Don't seem quite so amorous Over Shredded Wheat Nov 14 '05 #17

 P: n/a On Mon, 4 Apr 2005, Thomas Cameron wrote: I have an array of values which I would like to generate all possible combinations for. Does anybody know of the algorithm to produce this? c.f. http://www-cs-faculty.stanford.edu/~knuth/fasc3a.ps.gz --tobin Nov 14 '05 #18

 P: n/a Bob wrote: On Mon, 04 Apr 2005 16:30:53 +0200, Bob wrote:abcacbbacbcacababa Find the mistake ! aba should be cba. What do I win? -- Joe Wright mailto:jo********@comcast.net "Everything should be made as simple as possible, but not simpler." --- Albert Einstein --- Nov 14 '05 #19

 P: n/a Alan Balmer wrote: Eric Sosman wrote:Thomas Cameron wrote: [...] And example would be the values "a,b,c". This wouldproduce the following:aababcacbbcc Does anybody know of the algorithm to produce this? [...] Hint #2: One combination is missing from your list.Does the nature of the missing combination make Hint #1any clearer? No, it's there, though I'm not sure whether it's the line before "a" or the line after "c". Your eyes must not be very good if you can't see where it isn't. ;-) Suggested reading: "How can I have more if I have'n't had any?" Suggested reading #2: "Last night I met upon the stair / A little man who wasn't there. / He wasn't there again today. / I wish, I wish he'd go away!" -- Eric Sosman es*****@acm-dot-org.invalid Nov 14 '05 #20

### This discussion thread is closed

Replies have been disabled for this discussion.