combinatorics question

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

  1. Carnosaur

    Carnosaur Guest

    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
    #1
    1. Advertising

  2. Carnosaur

    Jake Roersma Guest

    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
    >


    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
    Jake Roersma, Oct 28, 2003
    #2
    1. Advertising

  3. Carnosaur

    David Rubin Guest

    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
    #3
  4. Carnosaur

    Lew Pitcher Guest

    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
    #4
  5. Carnosaur

    Lew Pitcher Guest

    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
    #5
  6. Carnosaur

    David Rubin Guest

    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
    David Rubin, Oct 28, 2003
    #6
  7. Carnosaur

    Carnosaur Guest

    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
    #7
  8. Carnosaur

    Mac Guest

    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
    #8
  9. (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
    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 */
    }
    }

    --
    Phil T
    Phil Tregoning, Oct 30, 2003
    #9
  10. Carnosaur

    pete Guest

    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
    #10
  11. Carnosaur

    Anupam Guest

    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
    #11
  12. Carnosaur

    David Rubin Guest

    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
    #12
  13. Carnosaur

    David Rubin Guest

    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
    #13
  14. Carnosaur

    Carnosaur Guest

    Re: combinatorics question-answered

    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
    #14
  15. Carnosaur

    Carnosaur Guest

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

    M
    Carnosaur, Oct 30, 2003
    #15
  16. (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
    #16
  17. 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
    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
    James Dow Allen, Oct 31, 2003
    #17
  18. Carnosaur

    Carnosaur Guest

    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
    #18
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Xah Lee

    [perl-python] combinatorics fun

    Xah Lee, Feb 10, 2005, in forum: Python
    Replies:
    7
    Views:
    382
    bruno modulix
    Feb 11, 2005
  2. Nic

    Python and Combinatorics

    Nic, May 16, 2006, in forum: Python
    Replies:
    4
    Views:
    1,712
    Gerard Flanagan
    May 16, 2006
  3. none

    Python and Combinatorics

    none, Oct 24, 2007, in forum: Python
    Replies:
    4
    Views:
    477
    Gerard Flanagan
    Oct 26, 2007
  4. Michael Robertson

    Combinatorics

    Michael Robertson, Feb 12, 2008, in forum: Python
    Replies:
    12
    Views:
    909
    Paul Hankin
    Feb 13, 2008
  5. Phlip
    Replies:
    4
    Views:
    309
    John Yeung
    Dec 2, 2009
Loading...

Share This Page