# combinatorics question

Discussion in 'C Programming' started by Carnosaur, Oct 28, 2003.

1. ### CarnosaurGuest

Hi all,

I am trying to write a program that will enumerate all possible
combinations of assigning 1 to 4 colors to 4 objects. For example,
there is one way to assign a single color to four objects, which might
be enumerated as:
1111

where each digit indicates an object and values indicate color.

Similarly there is one way to assign four colors to four objects:
1234

Similarly, here are the ways to assign two colors to four objects:
1112
1122
1222
1212

For my purposes, the specific colors are interchangeable (in other
words, 1112 is the same as 2221). All that matters is identifying and
enumerating patterns of shared or unique colors.

I would be extremely grateful to anyone that would help me with the
algorithm or C code for this problem. Although I can enumerate all
possibilities by hand for this simple case, I need to develop code for
the general problem of assigning (and enumerating) from 1 to k colors
to k objects. Thanks for any help!

Michael

Carnosaur, Oct 28, 2003

2. ### Jake RoersmaGuest

On Tue, 28 Oct 2003 10:12:05 -0800, Carnosaur wrote:

> Hi all,
>
> I am trying to write a program that will enumerate all possible
> combinations of assigning 1 to 4 colors to 4 objects. For example,
> there is one way to assign a single color to four objects, which might
> be enumerated as:
> 1111

http://www.eskimo.com/~scs/C-faq/top.html

> I would be extremely grateful to anyone that would help me with the
> algorithm or C code for this problem. Although I can enumerate all
> possibilities by hand for this simple case, I need to develop code for
> the general problem of assigning (and enumerating) from 1 to k colors
> to k objects. Thanks for any help!

that doesn't like to do homework for people. After he gets you going in
the right direction if you have problems with the C code post what you've
got and ask for help then.

> Michael
>

to do your homework. Some people may feel inclined to contact your
university or professor.

Regards,
Jake

Jake Roersma, Oct 28, 2003

3. ### David RubinGuest

Carnosaur wrote:
>
> Hi all,
>
> I am trying to write a program that will enumerate all possible
> combinations of assigning 1 to 4 colors to 4 objects. For example,
> there is one way to assign a single color to four objects, which might
> be enumerated as:
> 1111

Generating the enumerations is easy. The most straightforward way is to
have an array of integers where each index represents an object. Then,
you increase the values in a similar manner to an odometer.

[snip]
> For my purposes, the specific colors are interchangeable (in other
> words, 1112 is the same as 2221). All that matters is identifying and
> enumerating patterns of shared or unique colors.

This part is a bit more difficult. My first inclination is to define a
set of equivalence classes on the enumerations, and then store the each
unique equivalence. This might be straightforward. For example, You
stated that 1112 is equivalent to 2221. You can classify these datum as
31. Another example, is 1222, 3444, etc which are equivalent to 13. Yet
another example might be 1223, 1331, 3112, etc which are equivalent to
121. However, the precise classification is not clear from your
description.

/david

--
Andre, a simple peasant, had only one thing on his mind as he crept
along the East wall: 'Andre, creep... Andre, creep... Andre, creep.'
-- unknown

David Rubin, Oct 28, 2003
4. ### Lew PitcherGuest

David Rubin wrote:

> Carnosaur wrote:
>
>>Hi all,
>>
>>I am trying to write a program that will enumerate all possible
>>combinations of assigning 1 to 4 colors to 4 objects. For example,
>>there is one way to assign a single color to four objects, which might
>>be enumerated as:
>>1111

>
>
> Generating the enumerations is easy. The most straightforward way is to
> have an array of integers where each index represents an object. Then,
> you increase the values in a similar manner to an odometer.
>
> [snip]
>
>>For my purposes, the specific colors are interchangeable (in other
>>words, 1112 is the same as 2221). All that matters is identifying and
>>enumerating patterns of shared or unique colors.

>
>
> This part is a bit more difficult.

With a bit of math, it becomes easier.

The OP's problem starts of with
4 x 4 x 4 x 4
possible combinations of colours. If he enumerated all the possible values
in this range, he would enumerate all the possible colour combinations.

If I were trying to solve this sort of problem, instead of enumerating each
colour seperately (i.e. four nested loops), I would simply enumerate all the
colours as a range, and divide them out into seperate values.

For instance (untested code)

{
unsigned long palette;

for (palette = 0; palette < (4*4*4*4); ++palette)
{
unsigned long sample = palette;
char *colour[] = {"red","yellow","blue","green");

printf("%s, ",colour[sample%4]);
sample /= 4;
printf("%s, ",colour[sample%4]);
sample /= 4;
printf("%s, ",colour[sample%4]);
sample /= 4;
printf("%s\n",colour[sample%4]);
}
}

However, his later restrictions indicate that no colour may be repeated, and
this reduces his possibilities to
4 x 3 x 2 x 1
combinations. That's considerably fewer combinations to go through, although
the idea would be the same as before. For example (again, untested code)

{
unsigned long palette;

for (palette = 0; palette < (4*3*2*1); ++palette)
{
unsigned long sample = palette;
char *colour[] = {"red","yellow","blue","green");

printf("%s, ",colour[sample%4]);
sample /= 4;
printf("%s, ",colour[sample%4]);
sample /= 4;
printf("%s, ",colour[sample%4]);
sample /= 4;
printf("%s\n",colour[sample%4]);
}
}

--

Lew Pitcher, IT Consultant, Application Architecture
Enterprise Technology Solutions, TD Bank Financial Group

(Opinions expressed here are my own, not my employer's)

Lew Pitcher, Oct 28, 2003
5. ### Lew PitcherGuest

Lew Pitcher wrote:
[snip]
For example (again,
> untested code)
>
> {
> unsigned long palette;
>
> for (palette = 0; palette < (4*3*2*1); ++palette)
> {
> unsigned long sample = palette;
> char *colour[] = {"red","yellow","blue","green");
>
> printf("%s, ",colour[sample%4]);
> sample /= 4;
> printf("%s, ",colour[sample%4]);
> sample /= 4;
> printf("%s, ",colour[sample%4]);
> sample /= 4;
> printf("%s\n",colour[sample%4]);
> }
> }

But, then again, I would be wrong

--

Lew Pitcher, IT Consultant, Application Architecture
Enterprise Technology Solutions, TD Bank Financial Group

(Opinions expressed here are my own, not my employer's)

Lew Pitcher, Oct 28, 2003
6. ### David RubinGuest

Lew Pitcher wrote:
>
> David Rubin wrote:
>
> > Carnosaur wrote:
> >
> >>Hi all,
> >>
> >>I am trying to write a program that will enumerate all possible
> >>combinations of assigning 1 to 4 colors to 4 objects. For example,
> >>there is one way to assign a single color to four objects, which might
> >>be enumerated as:
> >>1111

> >
> >
> > Generating the enumerations is easy. The most straightforward way is to
> > have an array of integers where each index represents an object. Then,
> > you increase the values in a similar manner to an odometer.

[snip]
> If I were trying to solve this sort of problem, instead of enumerating each
> colour seperately (i.e. four nested loops), I would simply enumerate all the
> colours as a range, and divide them out into seperate values.

to the one I had in mind.

[snip]
> However, his later restrictions indicate that no colour may be repeated

I did not read this in OP's post. Rather, it seems that a combination
such as 1223 is valid, and this is not equivalent to 1234, but it is
equivalent to 2113.

My view is that there are 8 equivalency classes given 4 colors and 4
objects:

1111
112
13
121
211
22
31
4

Here, each digit represents the number of adjacent same-color values in
a particar enumeration. How do you arrive at this result? This seems to
be isomorphic to the problem of How Many Ways Can You Add To N?

/david

--
Andre, a simple peasant, had only one thing on his mind as he crept
along the East wall: 'Andre, creep... Andre, creep... Andre, creep.'
-- unknown

David Rubin, Oct 28, 2003
7. ### CarnosaurGuest

Thanks for the help.

let me define the problem in greater detail. I am dealing with four
parameters. Each parameter has a rate associated with it. Rates may
be shared across parameters, or each parameter may have a unique rate,
or some parameters may share some rates. Each unique pattern of rates
across the parameters defines a model.

So, if there are two rates, all four parameters have to take either
state 1 or state 2. However, 1112 is the same as 2221 because it
means the first three parameters have one rate and the fourth
parameter has a second rate.

Right now I use some incredibly redundant code to look at every
possiblity that I can think of and then store only the unique patterns
(see code below for 6 parameter case). However this seems like some
variant of an n choose k sort of problem, and I am interested in
eventually scaling up from four parameters (and four rates) to k
parameters and 1 to k rates, and doing it in a more elegant way.

Thanks for any help!

Michael

void EnumerateAllModels (void)

{

int whichCase, i, j, i1, i2, i3, i4, i5, i6, params[6], checked[6],
num, tempParams[6], tempParams2[6];

numModels = 0;
for (i=0; i<6; i++)
numOfNst = 0;

for (whichCase=0; whichCase<=10; whichCase++)
{
if (whichCase == 0)
{
params[0] = 0;
params[1] = 0;
params[2] = 0;
params[3] = 0;
params[4] = 0;
params[5] = 0;
}
else if (whichCase == 1)
{
params[0] = 0;
params[1] = 1;
params[2] = 1;
params[3] = 1;
params[4] = 1;
params[5] = 1;
}
else if (whichCase == 2)
{
params[0] = 0;
params[1] = 0;
params[2] = 1;
params[3] = 1;
params[4] = 1;
params[5] = 1;
}
else if (whichCase == 3)
{
params[0] = 0;
params[1] = 0;
params[2] = 0;
params[3] = 1;
params[4] = 1;
params[5] = 1;
}
else if (whichCase == 4)
{
params[0] = 0;
params[1] = 1;
params[2] = 2;
params[3] = 2;
params[4] = 2;
params[5] = 2;
}
else if (whichCase == 5)
{
params[0] = 0;
params[1] = 1;
params[2] = 1;
params[3] = 2;
params[4] = 2;
params[5] = 2;
}
else if (whichCase == 6)
{
params[0] = 0;
params[1] = 0;
params[2] = 1;
params[3] = 1;
params[4] = 2;
params[5] = 2;
}
else if (whichCase == 7)
{
params[0] = 0;
params[1] = 1;
params[2] = 2;
params[3] = 3;
params[4] = 3;
params[5] = 3;
}
else if (whichCase == 8)
{
params[0] = 0;
params[1] = 1;
params[2] = 2;
params[3] = 2;
params[4] = 3;
params[5] = 3;
}
else if (whichCase == 9)
{
params[0] = 0;
params[1] = 1;
params[2] = 2;
params[3] = 3;
params[4] = 4;
params[5] = 4;
}
else if (whichCase == 10)
{
params[0] = 0;
params[1] = 1;
params[2] = 2;
params[3] = 3;
params[4] = 4;
params[5] = 5;
}

for (i1=0; i1<6; i1++)
{
for (i2=0; i2<6; i2++)
{
if (i2 == i1)
continue;
for (i3=0; i3<6; i3++)
{
if (i3 == i1 || i3 == i2)
continue;
for (i4=0; i4<6; i4++)
{
if (i4 == i1 || i4 == i2 || i4 == i3)
continue;
for (i5=0; i5<6; i5++)
{
if (i5 == i1 || i5 == i2 || i5 == i3 || i5 == i4)
continue;
for (i6=0; i6<6; i6++)
{
if (i6 == i1 || i6 == i2 || i6 == i3 || i6 == i4 || i6 == i5)
continue;

tempParams[0] = params[i1];
tempParams[1] = params[i2];
tempParams[2] = params[i3];
tempParams[3] = params[i4];
tempParams[4] = params[i5];
tempParams[5] = params[i6];

for (i=0; i<6; i++)
checked = 0;
num = 0;
for (i=0; i<6; i++)
{
if (checked == 1)
continue;
tempParams2 = ++num;
for (j=i+1; j<6; j++)
{
if (checked[j] == 0 && tempParams == tempParams[j])
{
tempParams2[j] = num;
checked[j] = 1;
}
}
}

if (HasModelBeenFound(tempParams2) == NO)
{
models[numModels].index = numModels;
for (i=0; i<6; i++)
models[numModels].rateParams = tempParams2;

num = 0;
for (i=1; i<=6; i++)
{
for (j=0; j<6; j++)
if (models[numModels].rateParams[j] == i)
{
num++;
break;
}
}
models[numModels].nst = num;
numOfNst[num-1]++;
strcpy (models[numModels].name, "");
if (models[numModels].rateParams[0] == 1 &&
models[numModels].rateParams[1] == 1 &&
models[numModels].rateParams[2] == 1 &&
models[numModels].rateParams[3] == 1 &&
models[numModels].rateParams[4] == 1 &&
models[numModels].rateParams[5] == 1)
strcpy (models[numModels].name, "JC69/F81");
else if (models[numModels].rateParams[0] == 1 &&
models[numModels].rateParams[1] == 2 &&
models[numModels].rateParams[2] == 1 &&
models[numModels].rateParams[3] == 1 &&
models[numModels].rateParams[4] == 2 &&
models[numModels].rateParams[5] == 1)
strcpy (models[numModels].name, "K80/HKY85");
else if (models[numModels].rateParams[0] == 1 &&
models[numModels].rateParams[1] == 2 &&
models[numModels].rateParams[2] == 3 &&
models[numModels].rateParams[3] == 4 &&
models[numModels].rateParams[4] == 5 &&
models[numModels].rateParams[5] == 6)
strcpy (models[numModels].name, "EqualIn/GTR");
else if (models[numModels].rateParams[0] == 1 &&
models[numModels].rateParams[1] == 2 &&
models[numModels].rateParams[2] == 1 &&
models[numModels].rateParams[3] == 1 &&
models[numModels].rateParams[4] == 3 &&
models[numModels].rateParams[5] == 1)
strcpy (models[numModels].name, "TN93");

models[numModels].index = numModels + 1;
numModels++;
}

}
}
}
}
}
}

}

I
>
> This part is a bit more difficult. My first inclination is to define a
> set of equivalence classes on the enumerations, and then store the each
> unique equivalence. This might be straightforward. For example, You
> stated that 1112 is equivalent to 2221. You can classify these datum as
> 31. Another example, is 1222, 3444, etc which are equivalent to 13. Yet
> another example might be 1223, 1331, 3112, etc which are equivalent to
> 121. However, the precise classification is not clear from your
> description.
>
> /david

Carnosaur, Oct 28, 2003
8. ### MacGuest

On Tue, 28 Oct 2003 14:42:54 +0000, Carnosaur wrote:

> Thanks for the help.
>
> let me define the problem in greater detail. I am dealing with four
> parameters. Each parameter has a rate associated with it. Rates may
> be shared across parameters, or each parameter may have a unique rate,
> or some parameters may share some rates. Each unique pattern of rates
> across the parameters defines a model.
>
> So, if there are two rates, all four parameters have to take either
> state 1 or state 2. However, 1112 is the same as 2221 because it
> means the first three parameters have one rate and the fourth
> parameter has a second rate.
>
> Right now I use some incredibly redundant code to look at every
> possiblity that I can think of and then store only the unique patterns
> (see code below for 6 parameter case). However this seems like some
> variant of an n choose k sort of problem, and I am interested in
> eventually scaling up from four parameters (and four rates) to k
> parameters and 1 to k rates, and doing it in a more elegant way.
>

Why are you enumerating? I feel quite confident that the number of
combinations could be calculated without enumeration if all you want to
know is the final count. Even if you do want to enumerate, I think it
would be nice to know how many posibilities there are ahead of time.

The way I see it, is that you have to fill n slots with k colors, allowing
repetitions, but you want to ignore cases which differ by a color swap.

It's all about permutations and combinations. So I think you can start by
finding the number of ways to make the sum n with k integers, then
applying permutations and combinations. Or maybe just permutations.
Something like that. Anyway, they would probably know right away on a math
newsgroup.

> Thanks for any help!
>
> Michael
>

Good luck.

[code and other messages snipped]

Mac
--

Mac, Oct 30, 2003
9. ### Phil TregoningGuest

(Carnosaur) wrote in
news::

> Hi all,
>
> I am trying to write a program that will enumerate all possible
> combinations of assigning 1 to 4 colors to 4 objects. For example,
> there is one way to assign a single color to four objects, which might
> be enumerated as:
> 1111
>
> where each digit indicates an object and values indicate color.
>
> Similarly there is one way to assign four colors to four objects:
> 1234
>
> Similarly, here are the ways to assign two colors to four objects:
> 1112
> 1122
> 1222
> 1212

You missed out 1211, 1121 and 1221, or I have misunderstood

> For my purposes, the specific colors are interchangeable (in other
> words, 1112 is the same as 2221). All that matters is identifying and
> enumerating patterns of shared or unique colors.
>
> I would be extremely grateful to anyone that would help me with the
> algorithm or C code for this problem.

This probably belongs on comp.programming. Anyway, on the
assumption that I haven't misunderstood your requirements
one possible algorithm goes like this:

1: Start off with every object having no assigned colour
(i.e. colour 0)

2: Set the next colour to assign k to 1

3: Set the first unassigned object to color k.

4: For those objects that have no assigned colour, find every
possible combination of colour k assignements.

5. For each of these, if all objects have a colour, then it
is one possible combination. Otherwise, set k to k+1 and
go back to step 3.

This will build up a tree that looks something like this (ASCII
art alert, used a monospace font):

Step 3 Step 4 Step 3 Step 4 Step 3 Step 4 Step 3
k==1 k==1 k==2 k==2 k==3 k==3 k==4
------ ------ ------ ------ ------ ------ ------

+-> 1230 -> 1234
+-> 1200 -> 1230 |
| +-> 1233
|
+-> 1202 -> 1232
+-> 1000 -> 1200 |
| +-> 1220 -> 1223
| |
| +-> 1222
|
| +-> 1201 -> 1231
+-> 1001 -> 1201 |
| +-> 1221
|
| +-> 1210 -> 1213
+-> 1010 -> 1210 |
| +-> 1212
|
+-> 1011 -> 1211
1000 |
| +-> 1120 -> 1123
+-> 1100 -> 1120 |
| +-> 1122
|
+-> 1101 -> 1121
|
+-> 1110 -> 1112
|
+-> 1111

Here's my attempt at an implementation:

#include <stdio.h>

int first_unassigned(int obj[], int count, int after);
void comb(int obj[], int count, int k, int after);
void order(int obj[], int count, int k);
void print(int obj[], int count, int used_cols);

int main(int argc, char *argv[])
{
int obj[4] = {0}; /* Step 1 */
int k = 1; /* Step 2 */

order(obj, 4, k);
return 0;
}

void print(int obj[], int count, int used_cols)
{
int i;
printf("%d colours: ", used_cols);
for (i = 0 ; i < count ; i++) {
printf("%d", obj);
}
printf("\n");
}

int first_unassigned(int obj[], int count, int after)
{
int i;
for (i = after ; i < count ; i++) {
if (obj == 0) return i;
}
return -1;
}

void comb(int obj[], int count, int k, int after)
{
int first;

first = first_unassigned(obj, count, after);

if (first == -1) {
order(obj, count, k+1); /* Second half of Step 5 */
}
else {
comb(obj, count, k, first+1);
obj[first] = k;
comb(obj, count, k, first+1);
obj[first] = 0;
}
}

void order(int obj[], int count, int k)
{
int first;

first = first_unassigned(obj, count, 0);
if (first == -1) { /* First half of Step 5 */
print(obj, count, k-1);
}
else {
obj[first] = k; /* Step 3 */
comb(obj, count, k, first+1); /* Goto step 4 */
obj[first] = 0; /* Undo step 3 */
}
}

--
Phil T

Phil Tregoning, Oct 30, 2003
10. ### peteGuest

Carnosaur wrote:
>
> Hi all,
>
> I am trying to write a program that will enumerate all possible
> combinations of assigning 1 to 4 colors to 4 objects. For example,
> there is one way to assign a single color to four objects, which might
> be enumerated as:
> 1111
>
> where each digit indicates an object and values indicate color.
>
> Similarly there is one way to assign four colors to four objects:
> 1234
>
> Similarly, here are the ways to assign two colors to four objects:
> 1112
> 1122
> 1222
> 1212
>
> For my purposes, the specific colors are interchangeable (in other
> words, 1112 is the same as 2221). All that matters is identifying and
> enumerating patterns of shared or unique colors.

1111 = 1
2222 = 2
3333 = 4
4444 = 8

4321 = 15

55555 = 16
666666 = 32
7777777 = 64

There are 15 different ranks available.
If you had a 5, there'd be 31 different ranks available.

--
pete

pete, Oct 30, 2003
11. ### AnupamGuest

Re: combinatorics question : A possible algorithm

Hi,
Ok here goes,
Also, the previous object - color analogy is simple and good enough so
I dont see any reason to bring in the parameter - rate explanation.
In essence it is the equivalence class concept but stylised for
practical usage.
Assumption : n= No. of objects, k = No. of colors
Iterate a loop from 1 to n^n using i (say)
Find out what i is in base n ( Use repeated division as was manually
done in the example in 4 )
There should be thus, n digits.
Check for equivalence with previously generated pattern.
End of i loop

Now the best way to check for equivalence would be to store a linked
list of the equivalence class which the generated pattern is a special
case of. That way you could just check wheteher the newly generated
pattern is in a new equivalence class or not.
I have this funny feeling though that this is not the best possible
way. Look out for a way to directly generate the equivalence classes
themselves. As was rightly stated earlier, the right place to look for
that would be a math newsgroup. If you come across something better,
let us know.

Regards,
Anupam
[snipping all of it]

Anupam, Oct 30, 2003
12. ### David RubinGuest

Re: combinatorics question : A possible algorithm

Anupam wrote:

[snip]
> As was rightly stated earlier, the right place to look for

[the answer to a combinatorics problem]
> would be a math newsgroup.

So, you are suggesting that we computer scientists can't hack it alone?

/david

--
Andre, a simple peasant, had only one thing on his mind as he crept
along the East wall: 'Andre, creep... Andre, creep... Andre, creep.'
-- unknown

David Rubin, Oct 30, 2003
13. ### David RubinGuest

pete wrote:

> > For my purposes, the specific colors are interchangeable (in other
> > words, 1112 is the same as 2221). All that matters is identifying and
> > enumerating patterns of shared or unique colors.

>
> 1111 = 1
> 2222 = 2
> 3333 = 4
> 4444 = 8
>
> 4321 = 15
>
> 55555 = 16
> 666666 = 32
> 7777777 = 64

Obviously, this is a severely under-specified project. I haven't seen
two posts in this thread with the same interpretation of how to define
the equivalency classes.

/david

--
Andre, a simple peasant, had only one thing on his mind as he crept
along the East wall: 'Andre, creep... Andre, creep... Andre, creep.'
-- unknown

David Rubin, Oct 30, 2003
14. ### CarnosaurGuest

The messages in this topic have been extremely helpful, in spite of
the confusion I created by incorrectly enumerating cases in my
original message. Pete T (among others) hit it exactly. Thanks to
everyone who responded and sorry to those who found my post off-topic.

Michael
>
> Obviously, this is a severely under-specified project. I haven't seen
> two posts in this thread with the same interpretation of how to define
> the equivalency classes.
>
> /david

Carnosaur, Oct 30, 2003
15. ### CarnosaurGuest

err, thanks to Phil T (not Pete T) for the detailed explanation!

M

Carnosaur, Oct 30, 2003
16. ### Phil TregoningGuest

(Carnosaur) wrote in
news::

> err, thanks to Phil T (not Pete T) for the detailed explanation!
>

I've since realised there is a far simpler method. As an aside,
the number of different arrangements are:

1 Object : 1
2 Objects: 2
3 Objects: 5
4 Objects: 15
5 Objects: 52
6 Objects: 203
7 Objects: 877
8 Objects: 4140
9 Objects: 21147

A Google search reveals that these are Bell's Numbers, defined as
the number of ways a set with n elements can be partitioned into
disjoint, non-empty subsets, which sounds about right.

See for example http://www.pballew.net/Bellno.html

Anyhow, the far simpler method is:

#include <stdio.h>
#include <stdlib.h>

void comb(int obj[], int obj_count, int next_obj, int cols_used);
void print(int obj[], int obj_count, int cols_used);

int main(int argc, char *argv[])
{
int obj[4] = {0};
comb(obj, 4, 0, 0);
return 0;
}

void print(int obj[], int obj_count, int cols_used)
{
int i;

printf("%d colours: ", cols_used);
for (i = 0 ; i < obj_count ; i++) {
printf("%d", obj);
}
printf("\n");
}

void comb(int obj[], int obj_count, int next_obj, int cols_used)
{
int i;

if (next_obj == obj_count) {
print(obj, obj_count, cols_used);
}
else {
for (i = 1 ; i <= cols_used+1 ; i++) {
obj[next_obj] = i;
comb(obj, obj_count, next_obj+1,
i > cols_used ? i : cols_used);
}
}
}

--
Phil T

Phil Tregoning, Oct 31, 2003
17. ### James Dow AllenGuest

Combinatorics algorithms

(Carnosaur) wrote in message news:<>...

> I am trying to write a program that will enumerate all possible
> combinations of ...

Glancing at some of the messages in this thread, I find none satisfactory.

The need to iterate through combinations arises frequently;
and the best approaches are not straightforward. (The obvious nested loop
is tedious for large M, inefficient, and -- when one doesn't want to
precompute all combinations -- inappropriate for coroutine-like structure.)

The Nijenhuis-Wilf (spelling?) revolving-door algorithm is an
elegant way to generate combinations; Wilf and others have a variety of
beautiful algorithms for similar problems and it would be a shame to

Here's a URL to point you towards some of these algorithms.
Perhaps others can provide better URL's.

http://www.theory.cs.uvic.ca/~cos/dis/programs.html

James

James Dow Allen, Oct 31, 2003
18. ### CarnosaurGuest

Phil Tregoning <> wrote in message news:

This is exactly our problem! Thanks for the link--very satisfying.

M

>
> A Google search reveals that these are Bell's Numbers, defined as
> the number of ways a set with n elements can be partitioned into
> disjoint, non-empty subsets, which sounds about right.
>
> See for example http://www.pballew.net/Bellno.html
>

Carnosaur, Oct 31, 2003