Combinations problem

[Thomas Cameron]

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>drdabble s<dot>us
--
comp.lang.c.mod erated - moderation address: clcm@plethora.n et -- 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.

[hsomob1999@yahoo.com]

Re: Combinations problem

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

[Douglas A. Gwyn]

Re: Combinations problem

Thomas Cameron wrote:[color=blue]
>
> 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>drdabble s<dot>us
> --
> comp.lang.c.mod erated - moderation address: clcm@plethora.n et -- 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.[/color]

[Douglas A. Gwyn]

Re: Combinations problem

Thomas Cameron wrote:[color=blue]
> 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?[/color]

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

[Fred J. Tydeman]

Re: Combinations problem

Thomas Cameron wrote:[color=blue]
>
> 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.[/color]

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
tydeman@tybor.c om 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.

[Eden]

Re: Combinations problem

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

[David Resnick]

Re: Combinations problem

Thomas Cameron wrote:[color=blue]
> Hello all,
> I have an array of values which I would like to generate all[/color]
possible[color=blue]
> 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[/color]
the topic[color=blue]
> discussed, but never for strings or anything of the such. Most[/color]
discussion[color=blue]
> is regarding calculating the number of combinations... which I don't[/color]
care[color=blue]
> about.
>
> Thanks in advance,
> Tom Cameron
> tom<at>drdabble s<dot>us
> --
> comp.lang.c.mod erated - moderation address: clcm@plethora.n et -- you[/color]
must[color=blue]
> have an appropriate newsgroups line in your header for your mail to[/color]
be seen,[color=blue]
> or the newsgroup name in square brackets in the subject line. Sorry.[/color]

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(con st char *letters, int total_letters,
int current_letter, const char *prefix)
{
char *buf;
int i;

buf = malloc(strlen(l etters)+ 1);
if (buf == NULL) {
puts("malloc failure");
exit(EXIT_FAILU RE);
}

if (strlen(prefix) > 0) {
printf("%s\n", prefix);
}

for (i = current_letter; i < total_letters; i++) {
sprintf(buf, "%s%c", prefix, letters[i]);
printcombos(let ters, 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_FAILU RE);
}

printcombos(arg v[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

[Lawrence Kirby]

Re: Combinations problem

On Tue, 05 Apr 2005 11:38:15 -0700, David Resnick wrote:

....
[color=blue]
> 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[/color]

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

[Eden]

Re: Combinations problem

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

[Eden]

Re: Combinations problem

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:[color=blue]
> Hello all,
> I have an array of values which I would like to generate all[/color]
possible[color=blue]
> 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[/color]
the topic[color=blue]
> discussed, but never for strings or anything of the such. Most[/color]
discussion[color=blue]
> is regarding calculating the number of combinations... which I don't[/color]
care[color=blue]
> about.
>
> Thanks in advance,
> Tom Cameron
> tom<at>drdabble s<dot>us
> --
> comp.lang.c.mod erated - moderation address: clcm@plethora.n et -- you[/color]
must[color=blue]
> have an appropriate newsgroups line in your header for your mail to[/color]
be seen,[color=blue]
> or the newsgroup name in square brackets in the subject line. Sorry.[/color]

[David Resnick]

Re: Combinations problem

Lawrence Kirby wrote:[color=blue]
> On Tue, 05 Apr 2005 11:38:15 -0700, David Resnick wrote:
>
> ...
>[color=green]
> > 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[/color]
>
> Note you are generating a list of combinations, not permutations. You
> might argue that the lines above are all permutations but as a[/color]
permutation[color=blue]
> list it is highly incomplete. You typically use all or a specific[/color]
number[color=blue]
> of the elements in a permutation list and the order matters e.g. abcd[/color]
and[color=blue]
> dcba are distinct permutations. As the subject line indicates what
> you have are combinations.
>
> Lawrence[/color]

Yep, I used the wrong word. I meant "combinatio ns". 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

[CBFalconer]

Re: Combinations problem

Eden wrote:[color=blue]
>
> 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[/color]

Are you enjoying reposting this time after time, and ignoring all
the replies?

--
"If you want to post a followup via groups.google.c om, 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

[Urs Thuermann]

Re: Combinations problem

Thomas Cameron <tom@drdabbles. us> writes:
[color=blue]
> 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[/color]
[color=blue]
> Does anybody know of the algorithm to produce this? I've seen the
> topic discussed, but never for strings or anything of the such.[/color]

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

[Thad Smith]

Re: Combinations problem

Thomas Cameron wrote:[color=blue]
>
> 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?[/color]

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.mod erated - moderation address: clcm@plethora.n et -- 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.

[WillerZ]

Re: Combinations problem

Thomas Cameron wrote:[color=blue]
> 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".[/color]

I hope you mean "abc" or {'a','b','c'}, otherwise some more complex
string handling will be required.
[color=blue]
> This would
> produce the following:
>
> a
> ab
> abc
> ac
> b
> bc
> c[/color]

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" }.
[color=blue]
> 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.[/color]

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