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

Combinations in C?

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.

--
Tom Cameron
tom<at>drdabbles<dot>us
http://drdabbles.us
Nov 14 '05 #1
Share this Question
Share on Google+
19 Replies


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.


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!

--
Er*********@sun.com
Nov 14 '05 #2

P: n/a
Bob
On Mon, 04 Apr 2005 10:17:26 -0400, Eric Sosman <er*********@sun.com>
wrote:

... 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... :-)
Nov 14 '05 #3

P: n/a
Bob
On Mon, 04 Apr 2005 16:30:53 +0200, Bob <bo*@bob.bob> wrote:
abc
acb
bac
bca
cab
aba


Find the mistake !

Nov 14 '05 #4

P: n/a
In article <d2**********@news1brm.Central.Sun.COM>,
Eric Sosman <er*********@sun.com> wrote:

a
ab
abc
ac
b
bc
c
Hint #2: One combination is missing from your list.


How can you tell?

-- Richard
Nov 14 '05 #5

P: n/a
<posted & mailed>

Eric Sosman 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? 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!

--
Er*********@sun.com


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.
--
Tom Cameron
tom<at>drdabbles<dot>us
http://drdabbles.us
Nov 14 '05 #6

P: n/a

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.

--
Tom Cameron
tom<at>drdabbles<dot>us
http://drdabbles.us
Nov 14 '05 #7

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'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[i];
wd[i] = 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 */

--
"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 #8

P: n/a
Thomas Cameron wrote:
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
--
E-Mail: Mine is an /at/ gmx /dot/ de address.
Nov 14 '05 #9

P: n/a
<posted & mailed>

Michael Mair wrote:
Thomas Cameron wrote:
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
--
E-Mail: Mine is an /at/ gmx /dot/ de address.


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

--
Tom Cameron
tom<at>drdabbles<dot>us
http://drdabbles.us
Nov 14 '05 #10

P: n/a


Thomas Cameron wrote:
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. ...

--
Er*********@sun.com

Nov 14 '05 #11

P: n/a
<posted & mailed>

Eric Sosman wrote:
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. ...

--
Er*********@sun.com


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?

--
Tom Cameron
tom<at>drdabbles<dot>us
http://drdabbles.us
Nov 14 '05 #12

P: n/a


Thomas Cameron wrote:
<posted & mailed>
Not necessary; simply posting is fine.
Eric Sosman wrote:

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.


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.

--
Er*********@sun.com

Nov 14 '05 #13

P: n/a
On Mon, 04 Apr 2005 10:17:26 -0400, Eric Sosman <er*********@sun.com>
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? 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?


No, it's there, though I'm not sure whether it's the line before "a"
or the line after "c".
... and since there's an odor of homework about your
question, hints are all I'm willing to provide just now.
Good luck!


--
Al Balmer
Balmer Consulting
re************************@att.net
Nov 14 '05 #14

P: n/a
Eric Sosman <er*********@sun.com> wrote in
news:d2**********@news1brm.Central.Sun.COM:
Thomas Cameron wrote:
<posted & mailed>


Not necessary; simply posting is fine.


In fact, please do not email me.
Eric Sosman wrote:

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.


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

--
A. Sinan Unur <1u**@llenroc.ude.invalid>
(reverse each component and remove .invalid for email address)
Nov 14 '05 #15

P: n/a
Thomas Cameron wrote:
<posted & mailed>

Michael Mair wrote:
Thomas Cameron wrote:
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
--
E-Mail: Mine is an /at/ gmx /dot/ de address.

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

--
E-Mail: Mine is an /at/ gmx /dot/ de address.
Nov 14 '05 #16

P: n/a
Thomas Cameron wrote:
<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
--
The glances over cocktails
That seemed to be so sweet
Don't seem quite so amorous
Over Shredded Wheat
Nov 14 '05 #17

P: n/a
On Mon, 4 Apr 2005, Thomas Cameron wrote:
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

Nov 14 '05 #18

P: n/a
Bob wrote:
On Mon, 04 Apr 2005 16:30:53 +0200, Bob <bo*@bob.bob> wrote:

abc
acb
bac
bca
cab
aba

Find the mistake !


aba should be cba. What do I win?

--
Joe Wright mailto:jo********@comcast.net
"Everything should be made as simple as possible, but not simpler."
--- Albert Einstein ---
Nov 14 '05 #19

P: n/a
Alan Balmer wrote:
Eric Sosman <er*********@sun.com> wrote:
Thomas Cameron wrote:
[...] 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!"

--
Eric Sosman
es*****@acm-dot-org.invalid
Nov 14 '05 #20

This discussion thread is closed

Replies have been disabled for this discussion.