By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
 429,244 Members | 1,972 Online + Ask a Question
Need help? Post your question and get tips & solutions from a community of 429,244 IT Pros & Developers. It's quick & easy.

# Combinations problem

 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. Thanks in advance, Tom Cameron tomdrdabblesus -- comp.lang.c.moderated - moderation address: cl**@plethora.net -- you must have an appropriate newsgroups line in your header for your mail to be seen, or the newsgroup name in square brackets in the subject line. Sorry. Nov 14 '05 #1
Share this Question
15 Replies

 P: n/a what you need is a permutation algorithm. If you have a large set of items then that means a long wait. but if your set is small then its all wood. Just looking at the adds on the left you could check out www.cs.sunysb.edu to learn more. Then pass your NULL terminated ( of course) char array to the function U create. If you need more help, just ask..... Nov 14 '05 #2

 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. Thanks in advance, Tom Cameron tomdrdabblesus -- comp.lang.c.moderated - moderation address: cl**@plethora.net -- you must have an appropriate newsgroups line in your header for your mail to be seen, or the newsgroup name in square brackets in the subject line. Sorry. Nov 14 '05 #3

 P: n/a Thomas Cameron wrote: 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'm pretty sure this must be covered in Knuth, if not earlier then in one of the preliminary facsicles for Volume 4. Anyway, it is easy to figure out. Let's assume that all the array values are distinct, or if not that you want the duplicates that will be produced. (Otherwise, first sort the array then walk it and collapse it down to one instance each.) Then what you want can be characterized by: sets such that whether or not each element is present in the set varies through all possible combinations. That should ring a bell: presence = 1, absence = 0 => binary integer of width N where N = # elements. Thus all you have to do is enumerate the distinct possibilities for an N-bit integer, which can be done simply by counting, starting at 0. For each value of the counter, slide a 1-bit past it, ANDing to determine whether or not the corresponding position denotes the presence or the absence of that element. If present, output the token; if absent, do nothing. After the 1-bit has been slid N places, output a newline and increment the counter. Note that this will also output the empty string (no element present), which is a valid combination but which you might want to eliminate (so start the counter at 1 instead). Nov 14 '05 #4

 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. Sounds like you need to count in binary from 1 to 2**N-1 001 = c 010 = b 011 = bc 100 = a 101 = ac 110 = ab 111 = abc --- Fred J. Tydeman Tydeman Consulting ty*****@tybor.com Testing, numerics, programming +1 (775) 358-9748 Vice-chair of J11 (ANSI "C") Sample C99+FPCE tests: http://www.tybor.com Savers sleep well, investors eat well, spenders work forever. Nov 14 '05 #5

 P: n/a I don't know if there is any classic algorithm for this, but a quick-and-dirty approach I used once at a programming contest was to use binary numbers as flags into the array of symbols. For the case you mentioned: a, b, c = 3 symbols = pow(2,3) = 8. Mathematically, the first combination would be empty, so that would leave us 8 - 1 printable combinations: abc 001 = c 010 = b 011 = bc 100 = a 101 = ac 110 = ab 111 = abc Nov 14 '05 #6

 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. Thanks in advance, Tom Cameron tomdrdabblesus -- comp.lang.c.moderated - moderation address: cl**@plethora.net -- you must have an appropriate newsgroups line in your header for your mail to be seen, or the newsgroup name in square brackets in the subject line. Sorry. If you don't mind a recursive solution (blows up for big input sets), here is one. This is permuting characters, as in your example, but it could permute anything suitable modified... #include #include #include void printcombos(const char *letters, int total_letters, int current_letter, const char *prefix) { char *buf; int i; buf = malloc(strlen(letters)+ 1); if (buf == NULL) { puts("malloc failure"); exit(EXIT_FAILURE); } if (strlen(prefix) > 0) { printf("%s\n", prefix); } for (i = current_letter; i < total_letters; i++) { sprintf(buf, "%s%c", prefix, letters[i]); printcombos(letters, total_letters, i+1, buf); } free(buf); } int main(int argc, char **argv) { if (argc != 2) { puts("Need a single argument -- letters to be permuted"); exit(EXIT_FAILURE); } printcombos(argv, strlen(argv), 0, ""); return 0; } Sample run: temp(566)\$ gcc -ansi -pedantic -g -Wall -O -o permute permute.c temp(567)\$ permute abcd a ab abc abcd abd ac acd ad b bc bcd bd c cd d -David Nov 14 '05 #7

 P: n/a On Tue, 05 Apr 2005 11:38:15 -0700, David Resnick wrote: .... Sample run: temp(566)\$ gcc -ansi -pedantic -g -Wall -O -o permute permute.c temp(567)\$ permute abcd a ab abc abcd abd ac acd ad b bc bcd bd c cd d Note you are generating a list of combinations, not permutations. You might argue that the lines above are all permutations but as a permutation list it is highly incomplete. You typically use all or a specific number of the elements in a permutation list and the order matters e.g. abcd and dcba are distinct permutations. As the subject line indicates what you have are combinations. Lawrence Nov 14 '05 #8

 P: n/a I don't know if there's a classic optimized algorithm for this problem but a quick and dirty approach I used once in a programming contest consisted in using sequences of binary numbers as flags into the symbol array. Suppose you have an array [a, b, c], like the one you mentioned. The number of combinations in your case is given by pow(2, 3) wich will be equal to 8, because, mathematically, one of the combinations will be empty, that leaves us with 7 printable combinations: abc 1 001 = c 2 010 = b 3 011 = bc 4 100 = a 5 101 = ac 6 110 = ab 7 111 = abc Nov 14 '05 #9

 P: n/a I don't know if there's a classic optimized algorithm for this problem but a quick and dirty approach I used once in a programming contest consisted in using sequences of binary numbers as flags into the symbol array. Suppose you have an array [a, b, c], like the one you mentioned. The number of combinations in your case is given by pow(2, 3) wich will be equal to 8, because, mathematically, one of the combinations will be empty, that leaves us with 7 printable combinations: abc 1 001 = c 2 010 = b 3 011 = bc 4 100 = a 5 101 = ac 6 110 = ab 7 111 = abc 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. Thanks in advance, Tom Cameron tomdrdabblesus -- comp.lang.c.moderated - moderation address: cl**@plethora.net -- you must have an appropriate newsgroups line in your header for your mail to be seen, or the newsgroup name in square brackets in the subject line. Sorry. Nov 14 '05 #10

 P: n/a Lawrence Kirby wrote: On Tue, 05 Apr 2005 11:38:15 -0700, David Resnick wrote: ... Sample run: temp(566)\$ gcc -ansi -pedantic -g -Wall -O -o permute permute.c temp(567)\$ permute abcd a ab abc abcd abd ac acd ad b bc bcd bd c cd d Note you are generating a list of combinations, not permutations. You might argue that the lines above are all permutations but as a permutation list it is highly incomplete. You typically use all or a specific number of the elements in a permutation list and the order matters e.g. abcd and dcba are distinct permutations. As the subject line indicates what you have are combinations. Lawrence Yep, I used the wrong word. I meant "combinations". btw, I assumed that the code I posted would behave badly -- as in deep recursion -- for long strings, but it is OK. The recursion depth is only the length of the string, as I discovered by printing the current depth during a run, guess some examination would have shown that. So it isn't a bad solution, though the bitwise approach proposed by others seem like it may be easier/faster. For long strings the number of combinations is large (2^n - 1, or 2^n if the empty string is a combination). It takes a bit over 5 minutes on my workstation to do all combinations of the alphabet this way (a bit of a pokey machine). -David Nov 14 '05 #11

 P: n/a Eden wrote: I don't know if there's a classic optimized algorithm for this problem but a quick and dirty approach I used once in a programming contest consisted in using sequences of binary numbers as flags into the symbol array. Suppose you have an array [a, b, c], like the one you mentioned. The number of combinations in your case is given by pow(2, 3) wich will be equal to 8, because, mathematically, one of the combinations will be empty, that leaves us with 7 printable combinations: abc 1 001 = c 2 010 = b 3 011 = bc 4 100 = a 5 101 = ac 6 110 = ab 7 111 = abc Are you enjoying reposting this time after time, and ignoring all the replies? -- "If you want to post a followup via groups.google.com, don't use the broken "Reply" link at the bottom of the article. Click on "show options" at the top of the article, then click on the "Reply" at the bottom of the article headers." - Keith Thompson Nov 14 '05 #12

 P: n/a Thomas Cameron writes: 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. You mean a char array? Is it null-terminated? If so, this may do want you want: void f(char *s) { if (!*s) { putchar('\n'); return; f(s+1); putchar(*s); f(s+1); } urs Nov 14 '05 #13

 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? If all the items are distinct, it is straight-forward. Assume you have n items. Count from 0 to 2 ^ n in binary. Assign each bit position with an item from your set. For each binary number, generate the subset with the items corresponding to 1 bits in the number. Thad -- comp.lang.c.moderated - moderation address: cl**@plethora.net -- you must have an appropriate newsgroups line in your header for your mail to be seen, or the newsgroup name in square brackets in the subject line. Sorry. Nov 14 '05 #14

 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". I hope you mean "abc" or {'a','b','c'}, otherwise some more complex string handling will be required. This would produce the following: a ab abc ac b bc c what about cba, ba, cb, bca, etc? I assume you want only combinations in which the output elements are in the order they appeared in the input. I also assume that duplicate detection isn't required, meaning that "aaa" => { "a", "a", "a", "aa", "aa", "aa", "aaa" }. 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. There are two common ways to design this type of algorith. One way is to define a rule for ordering the elements of the set you wish to produce: once you work that out it is often easy to define a production rule which will emit the successor to any given element. The other way is to take an easy-to-calculate series and define a one-to-one mapping from that series to the desired output. I've used this method here. This C99 code will emit what you seem to be asking for, although not in the order you showed above: #include #include #include #include void print_combos ( size_t numelems, const char *input ) { char outbuf[numelems + 1]; size_t idx; // selector is an expensive implementation of a numelems-bit binary // integer. bool selector[numelems]; // We want to start at zero memset(selector, false, numelems); for (;;) { // Implement binary increment with overflow detection bool carry; idx = numelems; do { --idx; carry = selector[idx]; selector[idx] = !selector[idx]; } while (carry && (idx > 0)); // carry will only be true if the preceding increment overflowed if (carry) break; // now copy the selected elements into the output buffer size_t outpos = 0; for (idx = 0; idx < numelems; ++idx) if (selector[idx]) outbuf[outpos++] = input[idx]; // NUL-terminate it outbuf[outpos] = '\0'; // and print it puts(outbuf); } } C90-fication is left as an exercise for the interested reader... Nov 14 '05 #15

 P: n/a Thad Smith wrote: Thomas Cameron wrote:Hello all, I have an array of values which I would like to generate all possiblecombinations for. And example would be the values "a,b,c". This wouldproduce the following:aababcacbbcc Does anybody know of the algorithm to produce this? If all the items are distinct, it is straight-forward. Assume you have n items. Count from 0 to 2 ^ n in binary. Assign each bit position with an item from your set. For each binary number, generate the subset with the items corresponding to 1 bits in the number. Shuhel wrote (via email): Hello group, You misaddressed. Please reply to the newsgroup. I am new here. even in programming.. please make your answer clear to me. what you ment by distinct? It is good form to quote the part of the post you are referring to. By distinct, I mean that each element of the set generating the combination is different, e.g., {a,b,c}. If there are repetitions (elements are not distinct), such as {a,b,b,c}, you don't get 2^n combinations, and the generation is slightly more complicated. Thad -- comp.lang.c.moderated - moderation address: cl**@plethora.net -- you must have an appropriate newsgroups line in your header for your mail to be seen, or the newsgroup name in square brackets in the subject line. Sorry. Nov 14 '05 #16

### This discussion thread is closed

Replies have been disabled for this discussion. 