Velocity Reviews > combinatorics question

# combinatorics question

Carnosaur
Guest
Posts: n/a

 10-28-2003
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
http://www.velocityreviews.com/forums/(E-Mail Removed)

Jake Roersma
Guest
Posts: n/a

 10-28-2003
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

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 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
Guest
Posts: n/a

 10-28-2003
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

Lew Pitcher
Guest
Posts: n/a

 10-28-2003
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
Guest
Posts: n/a

 10-28-2003
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
Guest
Posts: n/a

 10-28-2003
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.

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

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

Carnosaur
Guest
Posts: n/a

 10-28-2003
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 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[i] = 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 ==
{
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[i] = 0;
num = 0;
for (i=0; i<6; i++)
{
if (checked[i] == 1)
continue;
tempParams2[i] = ++num;
for (j=i+1; j<6; j++)
{
if (checked[j] == 0 && tempParams[i] == 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[i] = tempParams2[i];

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

Mac
Guest
Posts: n/a

 10-30-2003
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
> (E-Mail Removed)

Good luck.

[code and other messages snipped]

Mac
--

Phil Tregoning
Guest
Posts: n/a

 10-30-2003
(E-Mail Removed) (Carnosaur) wrote in
news:(E-Mail Removed) m:

> 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[i]);
}
printf("\n");
}

int first_unassigned(int obj[], int count, int after)
{
int i;
for (i = after ; i < count ; i++) {
if (obj[i] == 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

pete
Guest
Posts: n/a

 10-30-2003
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

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Phlip Python 4 12-02-2009 05:35 AM Michael Robertson Python 12 02-13-2008 07:21 PM none Python 4 10-26-2007 07:41 AM Nic Python 4 05-16-2006 09:41 AM Xah Lee Python 7 02-11-2005 10:05 AM

Advertisments