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 19  7508 
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
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... :-)
On Mon, 04 Apr 2005 16:30:53 +0200, Bob <bo*@bob.bob> wrote: abc
acb
bac
bca
cab
aba
Find the mistake !
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
<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
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
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
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.
<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
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
<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
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
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
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)
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.
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
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 ---
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 This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Jim Hubbard |
last post by:
Does anyone have any code for doing combinations in VB.net or visual
basic ? I'd like to
be able to get an array of combinations (not permutations) of words from a
base group of words while...
|
by: rbt |
last post by:
Say I have a list that has 3 letters in it:
I want to print all the possible 4 digit combinations of those 3
letters:
4^3 = 64
aaaa
|
by: M a n i s h |
last post by:
i have been trying to build a program to find various combinations of a string.
the problem is that if there are multiple similar characters in the string
then the program displays multiple similar...
|
by: Thomas Cameron |
last post by:
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
|
by: Ryan |
last post by:
I've been trying to find an algorithm that will output all of the possible
combinations of items in an array. I know how to find the number of
combinations for each set using
nCr=n!/(r!(n-r)!)
...
|
by: GrantMagic |
last post by:
I have found that some strange combinations of characters in a URL can cause
an error in my ASP.NET application.
This is regarding URL Paramters
For example:
if i have the URL:...
|
by: Louis Aslett |
last post by:
I hope this is the correct newsgroup for this query (if not please
give me a pointer to where is best):
I understand the theory of normalisation etc and am trying to follow
best practices in the...
|
by: Bails |
last post by:
Hi all I have a theory for a lotto system and need help on how to code
it.
I want to create 1 massive database with EVERY combination of numbers
possible in a given lotto system, then remove all...
|
by: zgfareed |
last post by:
Can anyone suggest an algorithm or function to generate combinations/
permutations of a group of substrings stored in a vector. The
substrings consists of 3 letters and the resulting string...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: ryjfgjl |
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
| |
