switch algorithm, combo generation

[rogster001]

Hi all, i reseurrected an old project a few days ago, i have been having fun working old code and paring it down, improving where possible with the new techniques i have learnt since they were written.

However this code problem continues to give me a puzzle > I would like to know if anyone can see a way of optimising this, it generates the n combinations of n from n numbers.

it is important it actually produces the individual combos for testing against other data in the program, so i cant just use the known formula to calculate combinations.

my problem arises from needing to have the program adapt to an input case which can be a number from 2 to 6.
rather than always only generating combinations of 3 say.

it is just a big switch statement, i think it must be horribly inefficient because it looks that way, but can it be improved on..if thats not too hilarious to say!
it works and runs fast as it is, but with say combination 4 from 25 numbers being rather a lot, it then goes a little slower. i just cant think of any way around it, i would like to see if recursion could do it, but with different inputs i dont know.

I have posted a version that could handle combinations of 2, 3, or 4 from n numbers, the cases for 5 and 6 are succesively more convluted...so better to post the shorter ones..

example output with combolen = 2 and total_nums = 4 would be >
1, 2
1, 3
1, 4
2, 3
2, 4
3, 4

or e.g comboLen = 3, total_nums = 4 >
1,2,3
1,2,4
1,3,4
2,3,4

    //MAX_VAL is just a big number to break loop,
    // Anum, Bnum etc are ints
    //total_nums would be say 20, with comboLen 3
    //this would generate all the 3number combinations of 3 from 20.
    
    Anum = 1; Bnum = 2;Cnum = 3;Dnum = 4;Enum = 5; Fnum = 6;

    for(dwn = 0; dwn < MAX_VAL; dwn++)
    {
        combonum[0] = Anum;
        combonum[1] = Bnum;
        combonum[2] = Cnum;
        combonum[3] = Dnum;
        combonum[4] = Enum;
        combonum[5] = Fnum;

        //...FunctionCall(combonum)

         switch(comboLen)
         {
           case 2:
           {
                if(Bnum == total_nums)
                {
                    Anum++;
                    Bnum = Anum;
                }

                if(Anum == total_nums)
                dwn = MAX_VAL;

                Bnum++;
            break;
           }
           case 3:
           {
                if(Cnum == total_nums)
                {
                    Bnum++;
                    Cnum = Bnum;
                }
                if(Bnum+1 == total_nums)
                {
                    Cnum = Bnum;
                }
                if((Bnum == total_nums) && (Cnum == total_nums))
                {
                    Anum++;
                    Bnum = Anum+1;
                    Cnum = Bnum;
                }

                if(Anum+1 == total_nums)
                dwn = MAX_VAL;

                Cnum++;
             break;
           }
           case 4:
           {
                if(Dnum == total_nums)
                {
                    Cnum++;
                    Dnum = Cnum;
                }
                if(Cnum+1 == total_nums)
                {
                    Dnum = Cnum;
                }
                if(Cnum == total_nums)
                {
                    Bnum++;
                    Cnum = Bnum+1;
                    Dnum = Cnum;
                }
                if(Bnum+1 == total_nums)
                {
                    Anum++;
                    Bnum = Anum+1;
                    Cnum = Bnum+1;
                    Dnum = Cnum;
                }

                if(Anum+2 == total_nums)
                dwn = MAX_VAL;

                Dnum++;
           break;
           }
        }
     }

[giove]

I had some free time today and I try to write a recursive method for your code.
It is not a clean code, could be better, but could be a start point.
It works for any combination of combo size and numbers size.
have a look.

int *pcombonum,*pcombo;
int totalLen=20;       // Total numbers 
int comboLen=4;        // size of combo

void PrintOut(void)
{
    for (int i=0; i < comboLen; i++)
        printf("%d, ",pcombo[i]);
    printf("\n");
}

// fill the combo with the two last digits
void fullfill(int len,int total,int *pbase)
{
    int i,j;
    int tot=total;

    j=len-1;
    if (j < 0)
        return;
    printf("\n");
    for (i=0; i < total-len; i++)
    {
        pcombo[j]=pbase[i];
        PrintOut();
    }
    tot--;
    if ((tot-len)==0)
    {
        return;
    }
    if ((j-1) < 0)
        return;
    pcombo[j-1]=pbase[0];
    fullfill(len,tot,&pbase[1]);
}

int main()
{
    int i,j,k;

    int *pcombonew= new int[totalLen];
    int *pcombouse= new int[totalLen];

    if (comboLen > totalLen)
        comboLen=totalLen;

    pcombo= new int[comboLen];
    pcombonum= new int[totalLen];

    for (i=0;i < totalLen ; i++)  // First fillup of vector base;
        pcombonum[i]=i+1;

    for(j=0; j < totalLen-comboLen+1; j++)
    {
        int len=totalLen-j;
        for (i=0;i < totalLen-j; i++)
            pcombouse[i]=pcombonum[i+j];

        for (k=0; k < len-comboLen+1; k++)
        {
            for (i=0;i < len; i++)
                pcombonew[i]=pcombouse[i];

            for (i=comboLen-3; i < len-k;i++)
                pcombonew[i]=pcombouse[i+k];
        
            for (i=0; i < len; i++)    // Copy the first occurence
                pcombo[i]=pcombonew[i];
            fullfill(comboLen,len+1-k,&pcombonew[comboLen-1]); 

        }
    }
    printf("end recursive\n");
    getch();
    return 0;
}

[rogster001]

Hey thanks for the input, I will have a proper look when i can get a minute, its an interesting idea to fill the final numbers first i think? i have not looked properly yeet though

[rogster001]

It works but needs tweaking, it recurses too much haha, after the combinations are generated it feedsback on itself and does whole thing again from second number in, then from third number in etc. Also it's in cpp so would have to change slightly to test in the full code

[giove]

Yes, I wrote it as .cpp file, but I think is only a problem of new that must became malloc (and frre at the end).
For the recurse, I'll check, it seems regular.

[rogster001]

I ran it and heres the output for 3 from 5 >

1, 2, 3,
1, 2, 4,
1, 2, 5,

1, 3, 4,
1, 3, 5,

1, 4, 5,

2, 3, 4,
2, 3, 5,

2, 4, 5,

3, 4, 5, ------> This should be the end of function....

2, 3, 4,
2, 3, 5,

2, 4, 5,

3, 4, 5,

3, 4, 5,
end recursive

Also its nice to see it worked out as recursion as it looked tricky to do, but i do not think it will be any more efficient than the original, which is a lot simpler, naiive even but hey, i wonder if anyone could comment, using multiple function calls rather than reading a block branching statement, which is most efficient?

[giove]

You are right, with 3 & 5 this is the result. I'll have a look later.
Recursive's goal is to obtain an algorithm working with all combination of combo size and numbers.
I don't think mine is a good code, (NO: there are mistakes) it's an exercise I made, trying to solve this problem. It must be optimized or rewritten in a better way.

[iMalc]

Sorry rogster001, I only just noticed your PM.

This code is untested, but it would go something like this:

int combonum[MAX_VAL];
int high;
void printCombination(int n, int r)
{
    high = n;
    recurseCalcCombination(combonum, r);
}

void recurseCalcCombination(int a[], int nums, int low)
{
    if (nums <= 0)
    {
        //...FunctionCall(combonum);
        return;
    }
    for (int i=low; i <= high-nums+1; ++i)
    {
        a[0] = i;
        recurseCalcCombination(&a[1], nums-1, i+1);
    }
}

[rogster001]

wow man, so few lines! thats what i like to see! you are the maestro de los algoritmos, i am on phone at mo but will b in front of computer pronto and will test, thanks for having a look