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

 

[Douglas A. Gwyn]

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

 

[Douglas A. Gwyn]

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

 

[hsomob1999]

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

 

[Fred J. Tydeman]

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
(e-mail address removed) 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]

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]

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

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

 

[Lawrence Kirby]

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

 

[David Resnick]

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

...


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]

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]

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

 

[CBFalconer]

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?

 

[Urs Thuermann]

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

 

[Thad Smith]

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

 

[WillerZ]

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

 

[Thad Smith]

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