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
tom<at>drdabbles<dot>us

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. 15 2207
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.....
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 tom<at>drdabbles<dot>us  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.
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 Nbit integer, which can be
done simply by counting, starting at 0. For each value of
the counter, slide a 1bit 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 1bit 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).
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**N1
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) 3589748 Vicechair of J11 (ANSI "C")
Sample C99+FPCE tests: http://www.tybor.com
Savers sleep well, investors eat well, spenders work forever.
I don't know if there is any classic algorithm for this, but a
quickanddirty 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
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 tom<at>drdabbles<dot>us  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 <stdio.h>
#include <stdlib.h>
#include <string.h>
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[1], strlen(argv[1]), 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
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
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
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 tom<at>drdabbles<dot>us  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.
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
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
Thomas Cameron <to*@drdabbles.us> 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 nullterminated? 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
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 straightforward. 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.
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 easytocalculate series and define a
onetoone 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 <stddef.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
void
print_combos ( size_t numelems,
const char *input
)
{
char outbuf[numelems + 1];
size_t idx;
// selector is an expensive implementation of a numelemsbit 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];
// NULterminate it
outbuf[outpos] = '\0';
// and print it
puts(outbuf);
}
}
C90fication is left as an exercise for the interested reader...
Thad Smith 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?
If all the items are distinct, it is straightforward. 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. This discussion thread is closed Replies have been disabled for this discussion. Similar topics
reply
views
Thread by suzy 
last post: by

36 posts
views
Thread by rbt 
last post: by

2 posts
views
Thread by deancoo 
last post: by

7 posts
views
Thread by Micheal Artindale 
last post: by

1 post
views
Thread by M a n i s h 
last post: by

19 posts
views
Thread by Thomas Cameron 
last post: by

16 posts
views
Thread by akameswaran 
last post: by

2 posts
views
Thread by zgfareed 
last post: by

4 posts
views
Thread by rbr 
last post: by
          