Combinations in C?

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

 

[Eric Sosman]

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!

 

[Bob]

... and since there's an odor of homework about your
question, 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...

 

[Bob]

abc
acb
bac
bca
cab
aba

Find the mistake !

 

[Richard Tobin]

Hint #2: One combination is missing from your list.

How can you tell?

-- Richard

 

[Thomas Cameron]

<posted & mailed>

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!

Eric,
I can assure you that at 25 years old, I have no homework assigned to me.
Moreover, I believe my employer (www.timberland.com) would want to know
about any schooling I was attending that offered C courses, as they'd
gladly pay me for them. However, this is not the case.
The question I asked is in regards to a project I am working on personally
to test several command line options. Once I get this working I then have
two more for loops to add which will make the final algorithm Nx3x3
combinations. In other words, I'm expecting a rather absurd number of
combinations when all is said and done. (Perl output almost 80MB worth of
text from just the combinations without the for loops). Please note, PERL
is not a final solution to my problem, and I am not a PERL expert...thus
why I want to write this in C.

If anybody has an actual answer, that would be great. And thanks for your
help so far.

 

[Thomas Cameron]

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.

 

[CBFalconer]

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.

I've published this before in this group. Combining it with the
following alias is useful:

[1] c:\c\jumble>alias jumble
\c\jumble\jumble %1& | sort | uniq | pr -a -T --columns=8

---------------- cut here for jumble.c ---------------
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/* Public domain, by C.B. Falconer. *//* 2003-Aug-21 */
/* Attribution appreciated. */

/* Things get out of hand when larger than 8 */
#define MAXWORD 12

/* ------------------ */

/* exchange 0th and ith char in wd */
void trade(char *wd, unsigned int i)
{
char c;

c = *wd;
*wd = wd;
wd = c;
} /* trade */

/* ------------------ */

/* Form all n char permutations of the characters in the
string wd of length lgh into outstring at index ix.
Output the results to stdout. */
void jumble(char *wd, unsigned int lgh,
unsigned int ix, /* output place to fill */
unsigned int n, /* max out places to fill */
char *outstring)
{
unsigned int i;

if (0 == n) {
outstring[ix] = '\0';
puts(outstring);
}
else
for (i = 0; i < lgh; i++) {
trade(wd, i); /* nop when (0 == i) */
outstring[ix] = *wd;
jumble(wd+1, lgh-1, ix+1, n-1, outstring);
trade(wd, i); /* restore the wd string */
}
} /* jumble */

/* ------------------ */

int main(int argc, char *argv[])
{
unsigned int n, lgh, min;
double max;
char outstring[MAXWORD];

if (argc < 2) {
fprintf(stderr,
"Usage: jumble <baseword> [lgh]\n"
" where the (optional) lgh specifies the\n"
" maximum length of the output words\n");
return 0;
}
lgh = strlen(argv[1]);
if (lgh >= MAXWORD) argv[1][lgh = MAXWORD-1] = '\0';

min = lgh;
if ((argc > 2) && (1 == sscanf(argv[2], "%u", &n)))
if (n && (n <= lgh)) min = n;

for (n = lgh, max = 1.0; n > (lgh - min); n--)
max = max * n;

fprintf(stderr, "string=\"%s\", max=%.0f, len=%u\n",
argv[1], max, min);

jumble(argv[1], lgh, 0, min, outstring);
return 0;
} /* main, jumble.c */

 

[Michael Mair]

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

 

[Thomas Cameron]

<posted & mailed>

Hint #3
You have three "positions" to switch on or off (2 choices) which yields
2**3 possibilities... Something ringing?

Cheers
Michael

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

 

[Eric Sosman]

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

 

[Thomas Cameron]

<posted & mailed>

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

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?

 

[Eric Sosman]

<posted & mailed>

Not necessary; simply posting is fine.

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.

 

[Alan Balmer]

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?

No, it's there, though I'm not sure whether it's the line before "a"
or the line after "c".

 

[A. Sinan Unur]

Not necessary; simply posting is fine.

In fact, please do not email 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

 

[Michael Mair]

<posted & mailed>




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 <stdio.h>
#include <stdlib.h>
#include <limits.h>


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] : "<program>");
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<argc; testobj++) {
/* Checking this way is necessary for sorting the
** combination the desired right way */
if (combcount & (1UL << (argc-testobj-1)))
printf("%s ",argv[testobj]);
}
printf("\n");
} while (combcount != 0);

return 0;
}

 

[=?ISO-8859-1?Q?Gerg=F6_Barany?=]

<posted & mailed>

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

 

[Tobin Fricke]

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

 

[Joe Wright]

Find the mistake !

aba should be cba. What do I win?

 

[Eric Sosman]

[...] 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? [...]

Hint #2: One combination is missing from your list.
Does the nature of the missing combination make Hint #1
any 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!"