combinatorics question

[Carnosaur]

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

 

[Jake Roersma]

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

Start by reading this:

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!

I would ask your professor for help before you ask offtopic to a newsgroup
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
(e-mail address removed)

BTW, I'd leave your school email address out next time you ask for someone
to do your homework. Some people may feel inclined to contact your
university or professor.

Regards,
Jake

 

[David Rubin]

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

 

[Lew Pitcher]

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]

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)

 

[David Rubin]

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.

No one said anything about nested loops. Your implementation is similar
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

 

[Carnosaur]

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


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

 

[Mac]

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

Good luck.

[code and other messages snipped]

Mac
--

 

[Phil Tregoning]

(e-mail address removed) (Carnosaur) wrote in

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

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 */
}
}

 

[pete]

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.

 

[Anupam]

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]

 

[David Rubin]

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

 

[David Rubin]

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

 

[Carnosaur]

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

 

[Carnosaur]

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

M

 

[Phil Tregoning]

(e-mail address removed) (Carnosaur) wrote in

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

 

[James Dow Allen]

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
overlook them in this thread.

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

 

[Carnosaur]

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

M